#include<bits/stdc++.h>
#include <bubblesort2.h>
using namespace std;
const int N = 5e5;
const int M = 100;
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 >= 0;i&=(i + 1),i--){
fen[i]++;
}
}
int get(int pos){
int r = 0;
for(int i = pos;i < n;i|=(i + 1)){
r+=fen[i];
}
return r;
}
};
int fen2[N][M];
int n,q;
void add(int x,int y,int nr){
//cout<<"add:"<<x<<' '<<y<<' '<<nr<<'\n';
for(int i = x;i < n;i|=(i + 1)){
for(int j = y;j >= 0;j&=(j + 1),j--){
fen2[i][j]+=nr;
}
}
}
int get(int x,int y){
//cout<<"get:"<<x<<' '<<y<<' ';
int r = 0;
for(int i = x;i >= 0;i&=(i + 1),i--){
for(int j = y;j < M;j|=(j + 1)){
r+=fen2[i][j];
}
}
//cout<<r<<'\n';
return r;
}
set <int> last[M];
int p[N];
fenwick fen;
int cnt = 0;
vector <int> countScans(vector <int> v,vector <int> q1,vector <int> q2){
n = v.size();
q = q1.size();
bool ok = 0;
for(int i = 0;i < q;i++){
q2[i]--;
}
for(int i = 0;i < n;i++){
v[i]--;
if(v[i] >= 100)ok = 1;
if(v[i] < 100)last[v[i]].insert(i);
}
vector<int>ans;
if(ok){
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<<' ';
}
}else{
for(int i = 0;i < n;i++){
add(i,v[i],1);
}
for(int i = 0;i < q;i++){
add(q1[i],v[q1[i]],-1);
last[v[q1[i]]].erase(q1[i]);
v[q1[i]] = q2[i];
last[v[q1[i]]].insert(q1[i]);
add(q1[i],v[q1[i]],1);
int ans2 = 0;
/*for(int j = 0;j < n;j++){
ans2 = max(ans2,get(j - 1,v[j] + 1));
}*/
for(int j = 0;j < M;j++){
if(!last[j].empty()){
int x = *last[j].rbegin();
ans2 = max(ans2,get(x - 1,v[x] + 1));
}
}
ans.push_back(ans2);
//cout<<ans2<<'\n';
}
}
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 |
Incorrect |
15 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
16360 KB |
Output is correct |
2 |
Correct |
123 ms |
21676 KB |
Output is correct |
3 |
Correct |
209 ms |
26728 KB |
Output is correct |
4 |
Correct |
201 ms |
26776 KB |
Output is correct |
5 |
Correct |
224 ms |
27060 KB |
Output is correct |
6 |
Correct |
229 ms |
26836 KB |
Output is correct |
7 |
Correct |
280 ms |
26832 KB |
Output is correct |
8 |
Correct |
242 ms |
26828 KB |
Output is correct |
9 |
Correct |
222 ms |
26836 KB |
Output is correct |
10 |
Correct |
180 ms |
26744 KB |
Output is correct |
11 |
Correct |
181 ms |
26904 KB |
Output is correct |
12 |
Correct |
185 ms |
26788 KB |
Output is correct |
13 |
Correct |
170 ms |
26740 KB |
Output is correct |
14 |
Correct |
174 ms |
26892 KB |
Output is correct |
15 |
Correct |
170 ms |
26768 KB |
Output is correct |
16 |
Correct |
163 ms |
26836 KB |
Output is correct |
17 |
Correct |
168 ms |
26836 KB |
Output is correct |
18 |
Correct |
176 ms |
26728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
4444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |