#include<bits/stdc++.h>
#include <bubblesort2.h>
using namespace std;
const int N = 5e5;
vector <int> a;
vector <int> v2;
vector <int> x;
class fenwick{
int fen[N];
int n;
public:
void init(int sz){
n = sz;
for(int i = 0;i < n;i++)fen[i] = 0;
}
void add(int pos){
for(int i = pos;i < n;i|=(i + 1)){
fen[i]++;
}
}
int get(int pos){
int r = 0;
for(int i = pos;i >= 0;i&=(i + 1),i--){
r+=fen[i];
}
return r;
}
};
int p[N];
fenwick fen;
int cnt = 0;
vector <int> countScans(vector <int> v,vector <int> q1,vector <int> q2){
int n = v.size();
int q = q1.size();
vector<int>ans;
for(int i = 0;i < q;i++){
v[q1[i]] = q2[i];
fen.init(n);
int ans2 = 0;
for(int j = 0;j < n;j++)p[j] = j;
sort(p,p + n,[&](int a,int b){
if(v[a] == v[b])return a > b;
return v[a] > v[b];
});
for(int i = 0;i < n;i++){
ans2 = max(ans2,fen.get(p[i]));
fen.add(p[i]);
}
ans.push_back(ans2);
//cout<<ans2<<' ';
}
return ans;
}
/*int main(){
int n,q;
cin>>n>>q;
for(int i = 0;i < n;i++){
int b;
cin>>b;
a.push_back(b);
}
for(int i= 0;i < q;i++){
int b,c;
cin>>b>>c;
v2.push_back(c);
x.push_back(b);
}
countScans(a,x,v2);
return 0;
}*/
/**
4 2
1 2 3 4
0 3
2 1
**/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2392 KB |
Output is correct |
2 |
Correct |
42 ms |
2544 KB |
Output is correct |
3 |
Correct |
283 ms |
2584 KB |
Output is correct |
4 |
Correct |
280 ms |
2392 KB |
Output is correct |
5 |
Correct |
282 ms |
2396 KB |
Output is correct |
6 |
Correct |
173 ms |
2640 KB |
Output is correct |
7 |
Correct |
237 ms |
2596 KB |
Output is correct |
8 |
Correct |
256 ms |
2580 KB |
Output is correct |
9 |
Correct |
276 ms |
2544 KB |
Output is correct |
10 |
Correct |
293 ms |
2568 KB |
Output is correct |
11 |
Correct |
292 ms |
2644 KB |
Output is correct |
12 |
Correct |
291 ms |
2572 KB |
Output is correct |
13 |
Correct |
290 ms |
2652 KB |
Output is correct |
14 |
Correct |
295 ms |
2592 KB |
Output is correct |
15 |
Correct |
292 ms |
2580 KB |
Output is correct |
16 |
Correct |
295 ms |
2588 KB |
Output is correct |
17 |
Correct |
290 ms |
2584 KB |
Output is correct |
18 |
Correct |
298 ms |
2828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2392 KB |
Output is correct |
2 |
Correct |
42 ms |
2544 KB |
Output is correct |
3 |
Correct |
283 ms |
2584 KB |
Output is correct |
4 |
Correct |
280 ms |
2392 KB |
Output is correct |
5 |
Correct |
282 ms |
2396 KB |
Output is correct |
6 |
Correct |
173 ms |
2640 KB |
Output is correct |
7 |
Correct |
237 ms |
2596 KB |
Output is correct |
8 |
Correct |
256 ms |
2580 KB |
Output is correct |
9 |
Correct |
276 ms |
2544 KB |
Output is correct |
10 |
Correct |
293 ms |
2568 KB |
Output is correct |
11 |
Correct |
292 ms |
2644 KB |
Output is correct |
12 |
Correct |
291 ms |
2572 KB |
Output is correct |
13 |
Correct |
290 ms |
2652 KB |
Output is correct |
14 |
Correct |
295 ms |
2592 KB |
Output is correct |
15 |
Correct |
292 ms |
2580 KB |
Output is correct |
16 |
Correct |
295 ms |
2588 KB |
Output is correct |
17 |
Correct |
290 ms |
2584 KB |
Output is correct |
18 |
Correct |
298 ms |
2828 KB |
Output is correct |
19 |
Correct |
4059 ms |
3120 KB |
Output is correct |
20 |
Correct |
5322 ms |
3172 KB |
Output is correct |
21 |
Correct |
4348 ms |
3416 KB |
Output is correct |
22 |
Correct |
5161 ms |
3196 KB |
Output is correct |
23 |
Correct |
5316 ms |
3172 KB |
Output is correct |
24 |
Correct |
5356 ms |
3124 KB |
Output is correct |
25 |
Correct |
5340 ms |
3380 KB |
Output is correct |
26 |
Correct |
5305 ms |
2916 KB |
Output is correct |
27 |
Correct |
5378 ms |
2912 KB |
Output is correct |
28 |
Correct |
5284 ms |
3120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6101 ms |
3084 KB |
Output is correct |
2 |
Execution timed out |
9061 ms |
3668 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
2392 KB |
Output is correct |
2 |
Correct |
42 ms |
2544 KB |
Output is correct |
3 |
Correct |
283 ms |
2584 KB |
Output is correct |
4 |
Correct |
280 ms |
2392 KB |
Output is correct |
5 |
Correct |
282 ms |
2396 KB |
Output is correct |
6 |
Correct |
173 ms |
2640 KB |
Output is correct |
7 |
Correct |
237 ms |
2596 KB |
Output is correct |
8 |
Correct |
256 ms |
2580 KB |
Output is correct |
9 |
Correct |
276 ms |
2544 KB |
Output is correct |
10 |
Correct |
293 ms |
2568 KB |
Output is correct |
11 |
Correct |
292 ms |
2644 KB |
Output is correct |
12 |
Correct |
291 ms |
2572 KB |
Output is correct |
13 |
Correct |
290 ms |
2652 KB |
Output is correct |
14 |
Correct |
295 ms |
2592 KB |
Output is correct |
15 |
Correct |
292 ms |
2580 KB |
Output is correct |
16 |
Correct |
295 ms |
2588 KB |
Output is correct |
17 |
Correct |
290 ms |
2584 KB |
Output is correct |
18 |
Correct |
298 ms |
2828 KB |
Output is correct |
19 |
Correct |
4059 ms |
3120 KB |
Output is correct |
20 |
Correct |
5322 ms |
3172 KB |
Output is correct |
21 |
Correct |
4348 ms |
3416 KB |
Output is correct |
22 |
Correct |
5161 ms |
3196 KB |
Output is correct |
23 |
Correct |
5316 ms |
3172 KB |
Output is correct |
24 |
Correct |
5356 ms |
3124 KB |
Output is correct |
25 |
Correct |
5340 ms |
3380 KB |
Output is correct |
26 |
Correct |
5305 ms |
2916 KB |
Output is correct |
27 |
Correct |
5378 ms |
2912 KB |
Output is correct |
28 |
Correct |
5284 ms |
3120 KB |
Output is correct |
29 |
Correct |
6101 ms |
3084 KB |
Output is correct |
30 |
Execution timed out |
9061 ms |
3668 KB |
Time limit exceeded |
31 |
Halted |
0 ms |
0 KB |
- |