#include "bubblesort2.h"
#include <bits/stdc++.h>
#define Loop(x, l, r) for (ll x = (l); x < (r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
const int N = 1'000'010;
namespace seg {
int t[4*N];
int mx[4*N];
void add(int l, int r, int x, int i, int b, int e) {
if (l <= b && e <= r) {
t[i] += x;
mx[i] += x;
return;
}
if (r <= b || e <= l)
return;
add(l, r, x, 2*i+1, b, (b+e)/2);
add(l, r, x, 2*i+2, (b+e)/2, e);
mx[i] = t[i] + max(mx[2*i+1], mx[2*i+2]);
}
void add(int l, int r, int x) { add(l, r, x, 0, 0, N); }
int get() { return mx[0]; }
}
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
int n = A.size();
int q = X.size();
vector<pii> cmp;
Loop (i,0,n)
cmp.push_back({A[i], i});
Loop (i,0,q)
cmp.push_back({V[i], X[i]});
sort(cmp.begin(), cmp.end());
cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
Loop (i,0,n)
A[i] = lower_bound(cmp.begin(), cmp.end(), pii{A[i], i}) - cmp.begin();
Loop (i,0,q)
V[i] = lower_bound(cmp.begin(), cmp.end(), pii{V[i], X[i]}) - cmp.begin();
Loop (i,0,n) {
seg::add(A[i], A[i]+1, i);
seg::add(A[i]+1, cmp.size(), -1);
}
vector<int> ans;
Loop (j,0,q) {
int i = X[j];
seg::add(A[i], A[i]+1, -i);
seg::add(A[i]+1, cmp.size(), 1);
A[i] = V[j];
seg::add(A[i], A[i]+1, i);
seg::add(A[i]+1, cmp.size(), -1);
ans.push_back(seg::get());
}
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
4 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
468 KB |
Output is correct |
| 10 |
Correct |
4 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
468 KB |
Output is correct |
| 12 |
Correct |
4 ms |
468 KB |
Output is correct |
| 13 |
Correct |
4 ms |
468 KB |
Output is correct |
| 14 |
Correct |
4 ms |
580 KB |
Output is correct |
| 15 |
Correct |
4 ms |
468 KB |
Output is correct |
| 16 |
Correct |
4 ms |
468 KB |
Output is correct |
| 17 |
Correct |
4 ms |
468 KB |
Output is correct |
| 18 |
Correct |
4 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
4 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
468 KB |
Output is correct |
| 10 |
Correct |
4 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
468 KB |
Output is correct |
| 12 |
Correct |
4 ms |
468 KB |
Output is correct |
| 13 |
Correct |
4 ms |
468 KB |
Output is correct |
| 14 |
Correct |
4 ms |
580 KB |
Output is correct |
| 15 |
Correct |
4 ms |
468 KB |
Output is correct |
| 16 |
Correct |
4 ms |
468 KB |
Output is correct |
| 17 |
Correct |
4 ms |
468 KB |
Output is correct |
| 18 |
Correct |
4 ms |
468 KB |
Output is correct |
| 19 |
Correct |
15 ms |
980 KB |
Output is correct |
| 20 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 21 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 22 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 23 |
Correct |
17 ms |
980 KB |
Output is correct |
| 24 |
Correct |
17 ms |
1032 KB |
Output is correct |
| 25 |
Correct |
17 ms |
980 KB |
Output is correct |
| 26 |
Correct |
17 ms |
1016 KB |
Output is correct |
| 27 |
Correct |
17 ms |
1020 KB |
Output is correct |
| 28 |
Correct |
20 ms |
1108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 2 |
Correct |
68 ms |
2756 KB |
Output is correct |
| 3 |
Correct |
115 ms |
4968 KB |
Output is correct |
| 4 |
Correct |
117 ms |
4964 KB |
Output is correct |
| 5 |
Correct |
105 ms |
4932 KB |
Output is correct |
| 6 |
Correct |
112 ms |
4936 KB |
Output is correct |
| 7 |
Correct |
115 ms |
4928 KB |
Output is correct |
| 8 |
Correct |
114 ms |
4912 KB |
Output is correct |
| 9 |
Correct |
112 ms |
4976 KB |
Output is correct |
| 10 |
Correct |
108 ms |
4360 KB |
Output is correct |
| 11 |
Correct |
101 ms |
4320 KB |
Output is correct |
| 12 |
Correct |
104 ms |
4288 KB |
Output is correct |
| 13 |
Correct |
98 ms |
4348 KB |
Output is correct |
| 14 |
Correct |
102 ms |
4312 KB |
Output is correct |
| 15 |
Correct |
101 ms |
4312 KB |
Output is correct |
| 16 |
Correct |
99 ms |
4296 KB |
Output is correct |
| 17 |
Correct |
98 ms |
4252 KB |
Output is correct |
| 18 |
Correct |
99 ms |
4288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
340 KB |
Output is correct |
| 2 |
Correct |
2 ms |
468 KB |
Output is correct |
| 3 |
Correct |
4 ms |
468 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Correct |
4 ms |
468 KB |
Output is correct |
| 6 |
Correct |
4 ms |
468 KB |
Output is correct |
| 7 |
Correct |
4 ms |
468 KB |
Output is correct |
| 8 |
Correct |
4 ms |
468 KB |
Output is correct |
| 9 |
Correct |
4 ms |
468 KB |
Output is correct |
| 10 |
Correct |
4 ms |
468 KB |
Output is correct |
| 11 |
Correct |
4 ms |
468 KB |
Output is correct |
| 12 |
Correct |
4 ms |
468 KB |
Output is correct |
| 13 |
Correct |
4 ms |
468 KB |
Output is correct |
| 14 |
Correct |
4 ms |
580 KB |
Output is correct |
| 15 |
Correct |
4 ms |
468 KB |
Output is correct |
| 16 |
Correct |
4 ms |
468 KB |
Output is correct |
| 17 |
Correct |
4 ms |
468 KB |
Output is correct |
| 18 |
Correct |
4 ms |
468 KB |
Output is correct |
| 19 |
Correct |
15 ms |
980 KB |
Output is correct |
| 20 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 21 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 22 |
Correct |
17 ms |
1108 KB |
Output is correct |
| 23 |
Correct |
17 ms |
980 KB |
Output is correct |
| 24 |
Correct |
17 ms |
1032 KB |
Output is correct |
| 25 |
Correct |
17 ms |
980 KB |
Output is correct |
| 26 |
Correct |
17 ms |
1016 KB |
Output is correct |
| 27 |
Correct |
17 ms |
1020 KB |
Output is correct |
| 28 |
Correct |
20 ms |
1108 KB |
Output is correct |
| 29 |
Correct |
24 ms |
1488 KB |
Output is correct |
| 30 |
Correct |
68 ms |
2756 KB |
Output is correct |
| 31 |
Correct |
115 ms |
4968 KB |
Output is correct |
| 32 |
Correct |
117 ms |
4964 KB |
Output is correct |
| 33 |
Correct |
105 ms |
4932 KB |
Output is correct |
| 34 |
Correct |
112 ms |
4936 KB |
Output is correct |
| 35 |
Correct |
115 ms |
4928 KB |
Output is correct |
| 36 |
Correct |
114 ms |
4912 KB |
Output is correct |
| 37 |
Correct |
112 ms |
4976 KB |
Output is correct |
| 38 |
Correct |
108 ms |
4360 KB |
Output is correct |
| 39 |
Correct |
101 ms |
4320 KB |
Output is correct |
| 40 |
Correct |
104 ms |
4288 KB |
Output is correct |
| 41 |
Correct |
98 ms |
4348 KB |
Output is correct |
| 42 |
Correct |
102 ms |
4312 KB |
Output is correct |
| 43 |
Correct |
101 ms |
4312 KB |
Output is correct |
| 44 |
Correct |
99 ms |
4296 KB |
Output is correct |
| 45 |
Correct |
98 ms |
4252 KB |
Output is correct |
| 46 |
Correct |
99 ms |
4288 KB |
Output is correct |
| 47 |
Correct |
371 ms |
16324 KB |
Output is correct |
| 48 |
Correct |
1274 ms |
49176 KB |
Output is correct |
| 49 |
Correct |
1494 ms |
53184 KB |
Output is correct |
| 50 |
Correct |
1495 ms |
53164 KB |
Output is correct |
| 51 |
Correct |
1509 ms |
53168 KB |
Output is correct |
| 52 |
Correct |
1487 ms |
53212 KB |
Output is correct |
| 53 |
Correct |
1503 ms |
53128 KB |
Output is correct |
| 54 |
Correct |
1399 ms |
53280 KB |
Output is correct |
| 55 |
Correct |
1484 ms |
53364 KB |
Output is correct |
| 56 |
Correct |
1400 ms |
53332 KB |
Output is correct |
| 57 |
Correct |
1444 ms |
53340 KB |
Output is correct |
| 58 |
Correct |
1446 ms |
53244 KB |
Output is correct |
| 59 |
Correct |
1331 ms |
49956 KB |
Output is correct |
| 60 |
Correct |
1306 ms |
50036 KB |
Output is correct |
| 61 |
Correct |
1403 ms |
50160 KB |
Output is correct |
| 62 |
Correct |
1316 ms |
48860 KB |
Output is correct |
| 63 |
Correct |
1424 ms |
48936 KB |
Output is correct |
| 64 |
Correct |
1308 ms |
48864 KB |
Output is correct |
| 65 |
Correct |
1344 ms |
47708 KB |
Output is correct |
| 66 |
Correct |
1333 ms |
47708 KB |
Output is correct |
| 67 |
Correct |
1308 ms |
47708 KB |
Output is correct |
