Task: | Programmers |
Sender: | zscoder |
Submission time: | 2021-01-30 09:05:21 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 34 |
#2 | ACCEPTED | 21 |
#3 | ACCEPTED | 45 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#2 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#3 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#4 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#5 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#6 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#7 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#8 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#9 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#10 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#11 | ACCEPTED | 0.01 s | 1, 2, 3 | details |
#12 | ACCEPTED | 0.01 s | 1, 3 | details |
#13 | ACCEPTED | 0.01 s | 1, 3 | details |
#14 | ACCEPTED | 0.01 s | 1, 3 | details |
#15 | ACCEPTED | 0.01 s | 1, 3 | details |
#16 | ACCEPTED | 0.01 s | 1, 3 | details |
#17 | ACCEPTED | 0.13 s | 2, 3 | details |
#18 | ACCEPTED | 0.46 s | 2, 3 | details |
#19 | ACCEPTED | 0.43 s | 2, 3 | details |
#20 | ACCEPTED | 0.44 s | 2, 3 | details |
#21 | ACCEPTED | 0.44 s | 2, 3 | details |
#22 | ACCEPTED | 0.47 s | 2, 3 | details |
#23 | ACCEPTED | 0.50 s | 2, 3 | details |
#24 | ACCEPTED | 0.90 s | 3 | details |
#25 | ACCEPTED | 0.98 s | 3 | details |
#26 | ACCEPTED | 0.93 s | 3 | details |
#27 | ACCEPTED | 0.95 s | 3 | details |
#28 | ACCEPTED | 0.95 s | 3 | details |
#29 | ACCEPTED | 0.93 s | 3 | details |
#30 | ACCEPTED | 0.92 s | 3 | details |
#31 | ACCEPTED | 0.94 s | 3 | details |
Code
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define fi first #define se second #define mp make_pair #define pb push_back #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<int> vi; typedef long double ld; typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; typedef set<ll>::iterator sit; typedef map<ll,ll>::iterator mit; ll a[211111]; int n; map<ii, ll> ma; set<ii> intervals; ll res[211111]; void solve_fast(int k) { ma.clear(); intervals.clear(); multiset<pair<ll,ii> > pq; for(int i=0;i<n;i++) { pq.insert(mp(a[i], mp(i,i))); intervals.insert(mp(i,i)); ma[mp(i,i)] = a[i]; } ll ans = 0; for(int i=0;i<(n+1)/2;i++) { while(intervals.find((*prev(pq.end())).se)==intervals.end()) pq.erase(prev(pq.end())); ans += (*prev(pq.end())).fi; res[i+1] = ans; int l = (*prev(pq.end())).se.fi; int r = (*prev(pq.end())).se.se; auto it = intervals.find(mp(l,r)); auto itr = it; auto itl= it; itr++; itl--; vector<ii> era; if(it!=intervals.begin()) era.pb((*itl)); if(itr!=intervals.end()) era.pb((*itr)); if(itr!=intervals.end()&&it!=intervals.begin()) { int veryl = (*itl).fi; int veryr = (*itr).se; intervals.insert(mp(veryl,veryr)); ll V = ma[(*itl)] + ma[(*itr)] - ma[mp(l,r)]; ma[mp(veryl,veryr)] = V; pq.insert(mp(V, mp(veryl, veryr))); } intervals.erase(mp(l,r)); for(ii x:era) { intervals.erase(x); } } cout<<abs(res[k])<<'\n'; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin>>n; int k; cin>>k; vector<ll> x(n); for(int i=0;i<n;i++) cin>>x[i]; sort(x.begin(),x.end()); n--; for(int i=0;i<n;i++) { a[i]=x[i]-x[i+1]; } solve_fast(k); }
Test details
Test 1
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
8 3 3 1 2 7 9 3 4 7 |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2 1 2 13 |
correct output |
---|
11 |
user output |
---|
11 |
Test 3
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
20 10 16 20 6 15 19 12 11 17 20 6 15... |
correct output |
---|
6 |
user output |
---|
6 |
Test 4
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
14 5 11 3 8 3 14 8 10 13 11 10 17 1... |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
15 1 8 5 1 8 18 15 6 20 14 9 10 9 1... |
correct output |
---|
0 |
user output |
---|
0 |
Test 6
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
10 3 10 19 16 15 12 5 14 8 3 15 |
correct output |
---|
4 |
user output |
---|
4 |
Test 7
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
202 90 177 187 183 647 616 580 499 78... |
correct output |
---|
213 |
user output |
---|
213 |
Test 8
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 512 141 583 135 833 900 308 248 58... |
correct output |
---|
0 |
user output |
---|
0 |
Test 9
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 972 685 4 289 865 93 159 48 866 56... |
correct output |
---|
276 |
user output |
---|
276 |
Test 10
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 1000 698 153 298 118 631 341 238 7 ... |
correct output |
---|
517 |
user output |
---|
517 |
Test 11
Group: 1, 2, 3
Verdict: ACCEPTED
input |
---|
2000 1 983 144 449 584 839 166 77 885... |
correct output |
---|
0 |
user output |
---|
0 |
Test 12
Group: 1, 3
Verdict: ACCEPTED
input |
---|
1464 320 846762124 954854396 12767390 7... |
correct output |
---|
35809369 |
user output |
---|
35809369 |
Test 13
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 231 801945178 924940258 369188694 ... |
correct output |
---|
7831421 |
user output |
---|
7831421 |
Test 14
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 461 464790475 932031556 838378103 ... |
correct output |
---|
37272564 |
user output |
---|
37272564 |
Test 15
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 100 484046702 267135814 995006323 ... |
correct output |
---|
1268400 |
user output |
---|
1268400 |
Test 16
Group: 1, 3
Verdict: ACCEPTED
input |
---|
2000 996 98352148 438929491 242618159 1... |
correct output |
---|
445965905 |
user output |
---|
445965905 |
Test 17
Group: 2, 3
Verdict: ACCEPTED
input |
---|
65879 19675 896 316 972 476 636 227 716 78... |
correct output |
---|
0 |
user output |
---|
0 |
Test 18
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 53820 995 720 135 767 943 742 191 26... |
correct output |
---|
0 |
user output |
---|
0 |
Test 19
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 32297 527 947 84 851 908 833 339 112... |
correct output |
---|
0 |
user output |
---|
0 |
Test 20
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 99982 561 174 242 275 460 109 664 68... |
correct output |
---|
322 |
user output |
---|
322 |
Test 21
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 99955 911 33 314 861 298 117 972 982... |
correct output |
---|
245 |
user output |
---|
245 |
Test 22
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 99972 783 1000 673 611 87 452 702 92... |
correct output |
---|
290 |
user output |
---|
290 |
Test 23
Group: 2, 3
Verdict: ACCEPTED
input |
---|
200000 99961 795 136 128 643 60 422 371 839... |
correct output |
---|
252 |
user output |
---|
252 |
Test 24
Group: 3
Verdict: ACCEPTED
input |
---|
195426 76599 442872072 619088799 118541378 ... |
correct output |
---|
143376538 |
user output |
---|
143376538 |
Test 25
Group: 3
Verdict: ACCEPTED
input |
---|
200000 1661 894106972 620084612 931442312 ... |
correct output |
---|
33089 |
user output |
---|
33089 |
Test 26
Group: 3
Verdict: ACCEPTED
input |
---|
200000 86032 211444153 846442677 297198384 ... |
correct output |
---|
196001810 |
user output |
---|
196001810 |
Test 27
Group: 3
Verdict: ACCEPTED
input |
---|
200000 28275 28280312 349705372 96535649 84... |
correct output |
---|
11627219 |
user output |
---|
11627219 |
Test 28
Group: 3
Verdict: ACCEPTED
input |
---|
200000 81473 178022892 112774306 250584651 ... |
correct output |
---|
162430841 |
user output |
---|
162430841 |
Test 29
Group: 3
Verdict: ACCEPTED
input |
---|
200000 99987 297598052 494409138 182268523 ... |
correct output |
---|
489497036 |
user output |
---|
489497036 |
Test 30
Group: 3
Verdict: ACCEPTED
input |
---|
200000 99971 316462272 843156468 434342923 ... |
correct output |
---|
483167476 |
user output |
---|
483167476 |
Test 31
Group: 3
Verdict: ACCEPTED
input |
---|
200000 99964 811543559 465033274 620180191 ... |
correct output |
---|
481497328 |
user output |
---|
481497328 |