Task: | Kaaleppi's run |
Sender: | OOliOO_slayer |
Submission time: | 2016-10-04 18:41:05 +0300 |
Language: | C++ |
Status: | READY |
Result: | TIME LIMIT EXCEEDED |
test | verdict | time | |
---|---|---|---|
#1 | TIME LIMIT EXCEEDED | -- | details |
#2 | TIME LIMIT EXCEEDED | -- | details |
#3 | TIME LIMIT EXCEEDED | -- | details |
#4 | TIME LIMIT EXCEEDED | -- | details |
#5 | TIME LIMIT EXCEEDED | -- | details |
#6 | ACCEPTED | 1.76 s | details |
#7 | TIME LIMIT EXCEEDED | -- | details |
#8 | ACCEPTED | 0.14 s | details |
#9 | TIME LIMIT EXCEEDED | -- | details |
#10 | TIME LIMIT EXCEEDED | -- | details |
#11 | TIME LIMIT EXCEEDED | -- | details |
#12 | TIME LIMIT EXCEEDED | -- | details |
#13 | TIME LIMIT EXCEEDED | -- | details |
#14 | TIME LIMIT EXCEEDED | -- | details |
#15 | TIME LIMIT EXCEEDED | -- | details |
#16 | TIME LIMIT EXCEEDED | -- | details |
#17 | TIME LIMIT EXCEEDED | -- | details |
#18 | TIME LIMIT EXCEEDED | -- | details |
#19 | TIME LIMIT EXCEEDED | -- | details |
#20 | TIME LIMIT EXCEEDED | -- | details |
#21 | TIME LIMIT EXCEEDED | -- | details |
#22 | TIME LIMIT EXCEEDED | -- | details |
#23 | TIME LIMIT EXCEEDED | -- | details |
#24 | TIME LIMIT EXCEEDED | -- | details |
#25 | TIME LIMIT EXCEEDED | -- | details |
#26 | TIME LIMIT EXCEEDED | -- | details |
#27 | TIME LIMIT EXCEEDED | -- | details |
#28 | TIME LIMIT EXCEEDED | -- | details |
#29 | TIME LIMIT EXCEEDED | -- | details |
#30 | TIME LIMIT EXCEEDED | -- | details |
Code
#include <stdio.h> // include before iostream for faster scanf #include <iostream> #include <vector> #include <string> #include <map> #include <unordered_map> #include <algorithm> #include <utility> #include <set> #include <unordered_set> #include <cmath> #include <math.h> #include <queue> #include <stdlib.h> #include <string.h> #include <sstream> #include <tuple> #include <utility> #include <iomanip> #include <iterator> using namespace std; typedef long long LL; #define printv(printVec) for (auto printVecIter : (printVec)) cout << printVecIter << " "; cout << endl; // g++-4.8 -Wall -Wshadow -std=c++11 a.cpp && ./a.out int SZ = 3; int main() { std::ios::sync_with_stdio(false);cin.tie(0); int n, q; cin >> n>>q; typedef pair<int,int> pii; typedef priority_queue<pii, vector<pii>> pq; vector<int> v(n); for (int i = 0; i < n; i++) { cin >> v[i]; } //vector<vector<pair<int,int>>> sq(n/SZ + 2); vector<pq> sq(n/SZ + 2); vector<LL> sums(n/SZ + 2); for (int i = 0; i < n; i++) { sq[i/SZ].emplace(v[i],i); sums[i/SZ] += v[i]; } while (q--) { int type; cin >> type; if (type == 2) { //cout<<endl; //printv(v); int l,r; cin>>l>>r; l--; r--; LL ans = 0; for (int i = l; i <= r; i++) { if (i + SZ < r && (i % SZ) == 0) { int block = i / SZ; ans += sums[block]; i += SZ - 1; } else { ans += v[i]; } } cout << ans <<"\n"; continue; } int l,r,k; cin>>l>>r>>k; l--;r--; for (int i = l; i <= r; i++) { if (i + SZ < r && (i % SZ) == 0) { int block = i / SZ; while (sq[block].top().first >= k || v[sq[block].top().second] >= k) { //cout <<q<<" "<<i << " " << sq[block].top().first << " MODIFyING " << sq[block].top().second <<endl; int val, idx; tie(val, idx) = sq[block].top(); sq[block].pop(); sums[block] -= v[idx]; v[idx] = v[idx] % k; sums[block] += v[idx]; sq[block].emplace(v[idx], idx); //cout <<sq[block].size() << " "<<sq[block].top().first << " NEWTOP " << sq[block].top().second <<endl; } i += SZ - 1; } else { sums[i/SZ] -= v[i]; v[i] = v[i] % k; sums[i/SZ] += v[i]; } } } }
Test details
Test 1
Verdict: TIME LIMIT EXCEEDED
input |
---|
89384 130887 681692778 714636916 957747794 ... |
correct output |
---|
3568050627345 4840079633895 4979742617229 3278015536236 8227531490884 ... |
user output |
---|
(empty) |
Test 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
110132 199724 847570814 404978775 106367318 ... |
correct output |
---|
1427981161528 6256316123063 1076159707539 1525408287745 12452883393272 ... |
user output |
---|
(empty) |
Test 3
Verdict: TIME LIMIT EXCEEDED
input |
---|
87738 181088 562855988 84781032 926253527 7... |
correct output |
---|
5716947015138 14424560752621 3616168262601 807226877121 83465638349 ... |
user output |
---|
(empty) |
Test 4
Verdict: TIME LIMIT EXCEEDED
input |
---|
158114 63223 462120872 498977056 463223297 ... |
correct output |
---|
49126485898374 2184603743669 23961846093944 2848201705457 1555275733993 ... |
user output |
---|
(empty) |
Test 5
Verdict: TIME LIMIT EXCEEDED
input |
---|
140966 138126 812693646 252682523 265941575 ... |
correct output |
---|
22817793228905 17812780427335 2620152643855 2866263272648 5009940526564 ... |
user output |
---|
(empty) |
Test 6
Verdict: ACCEPTED
input |
---|
70958 64685 892097055 124053711 989231834 ... |
correct output |
---|
460637799671 1475480287645 3957671266357 15189222079188 8068328407783 ... |
user output |
---|
460637799671 1475480287645 3957671266357 15189222079188 8068328407783 ... |
Test 7
Verdict: TIME LIMIT EXCEEDED
input |
---|
97044 123753 707926206 599809760 994891636 ... |
correct output |
---|
30504891581 10585850358828 3752130598295 4274674534895 18961318419991 ... |
user output |
---|
(empty) |
Test 8
Verdict: ACCEPTED
input |
---|
25458 9623 313230374 496638350 562858459 ... |
correct output |
---|
348560018107 5323872135694 28101423541 5060603534783 8455422896644 ... |
user output |
---|
348560018107 5323872135694 28101423541 5060603534783 8455422896644 ... |
Test 9
Verdict: TIME LIMIT EXCEEDED
input |
---|
161390 197159 674040671 808300128 26080705 9... |
correct output |
---|
6338494962280 9308586268339 1426570147836 619729941732 531996459059 ... |
user output |
---|
(empty) |
Test 10
Verdict: TIME LIMIT EXCEEDED
input |
---|
183342 96224 100979382 831921884 895353059 ... |
correct output |
---|
4146493190203 29755052359871 21010351347658 4994403502744 4874048764601 ... |
user output |
---|
(empty) |
Test 11
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 163516132 88718522 960501684 3... |
correct output |
---|
8705161776177 16560680715170 4529140494185 22215511151267 307663601912 ... |
user output |
---|
(empty) |
Test 12
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 661328518 295428034 543539165 ... |
correct output |
---|
44125316835086 12534063038672 13779878669135 1110457357385 53890550863397 ... |
user output |
---|
(empty) |
Test 13
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 835492064 858947595 489705704 ... |
correct output |
---|
7123736494948 18343643800481 4061553943570 22394824679259 17059560008797 ... |
user output |
---|
(empty) |
Test 14
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 357734101 493956933 250155363 ... |
correct output |
---|
19974989429712 60252072248233 45678027522989 9906096645143 5796576869969 ... |
user output |
---|
(empty) |
Test 15
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 366056556 485208318 898983115 ... |
correct output |
---|
18324415144074 1960721236822 262868810399 418650395034 4926733633202 ... |
user output |
---|
(empty) |
Test 16
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 696545081 391575800 525194671 ... |
correct output |
---|
464526195732 10421706643804 25715510077679 60768424352308 47109574794106 ... |
user output |
---|
(empty) |
Test 17
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 785409780 12543965 724522794 5... |
correct output |
---|
76078073776916 12550437486909 1961851552333 3704172183345 958583269110 ... |
user output |
---|
(empty) |
Test 18
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 239188181 76186945 538812873 7... |
correct output |
---|
9965856033901 22841982053808 20057247487740 22036414753777 743665836923 ... |
user output |
---|
(empty) |
Test 19
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 571088696 713137765 869808231 ... |
correct output |
---|
27201871131366 1773925165749 21331314450495 44597922896 11839927329463 ... |
user output |
---|
(empty) |
Test 20
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 94357126 167500952 625424533 7... |
correct output |
---|
19827596131079 1587873460955 56673140705204 1825224125411 14126369552503 ... |
user output |
---|
(empty) |
Test 21
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 902289752 980717302 482700427 ... |
correct output |
---|
42722728269555 32652085471516 7532635788308 26365360928406 31706902704494 ... |
user output |
---|
(empty) |
Test 22
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 234861789 896308950 585257292 ... |
correct output |
---|
23148184769579 6264813675999 47314176314048 17697735609162 2251160486380 ... |
user output |
---|
(empty) |
Test 23
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 889896556 543224603 961078149 ... |
correct output |
---|
1713650642846 35249443235523 9622564970592 20993151478096 559043197323 ... |
user output |
---|
(empty) |
Test 24
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 995332283 686573056 932431685 ... |
correct output |
---|
12013196028573 47655633640876 18257672284868 27625651650511 46438192959164 ... |
user output |
---|
(empty) |
Test 25
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 946315600 868557890 318443283 ... |
correct output |
---|
1133762533395 57398145786924 869840469415 29146044858314 35199351262230 ... |
user output |
---|
(empty) |
Test 26
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 944060128 254626749 68890590 2... |
correct output |
---|
11055994363482 2657055498612 30597070068344 7792687527844 7661261162964 ... |
user output |
---|
(empty) |
Test 27
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 841299688 308557219 620166698 ... |
correct output |
---|
19393456997210 195469629029 2786427435737 1993020037538 3164725175677 ... |
user output |
---|
(empty) |
Test 28
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 494252927 946174799 609845025 ... |
correct output |
---|
15907022632481 27292668068962 441027352490 40834476272262 28481559993407 ... |
user output |
---|
(empty) |
Test 29
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 470856857 625269921 288612820 ... |
correct output |
---|
2046228565150 3617420568401 1053973762226 5913120807902 5419236217968 ... |
user output |
---|
(empty) |
Test 30
Verdict: TIME LIMIT EXCEEDED
input |
---|
200000 200000 62623182 70087409 956344115 19... |
correct output |
---|
28081481609073 287568565804 2709243279569 5210936812890 12514447288598 ... |
user output |
---|
(empty) |