//fast
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(),x.end()
#define rep(n) for (int i = 0 ; i<n ; i++)
#define pb push_back
const int base = (1<<20);
int maks[base*2];
int sum[base*2];
set<int> pos[base];
int stala[base];
void printout(){
cout << " " << maks[1] << '\n';
cout << " " << maks[2] << " " << maks[3] << '\n';
cout << maks[4] << ' ' << maks[5] << ' ' << maks[6] << ' ' << maks[7] << '\n';
cout << " " << sum[1] << '\n';
cout << " " << sum[2] << " " << sum[3] << '\n';
cout << sum[4] << ' ' << sum[5] << ' ' << sum[6] << ' ' << sum[7] << '\n';
cout << stala[0] << ' ' << stala[1] << ' ' << stala[2] << ' ' << stala[3] << '\n';
}
void dodaj(int l, int r, int p, int k, int w, int c){
if (k<l || r<p) return;
if (p<=l && r<=k){
sum[w]+=c;
maks[w]+=c;
return;
}
dodaj(l,(l+r)/2,p,k,w*2,c);
dodaj((l+r)/2+1,r,p,k,w*2+1,c);
maks[w] = max(maks[w*2],maks[w*2+1])+sum[w];
}
void ustaw(int a, int b){
sum[a+base]-=stala[a];
stala[a] = b;
sum[a+base]+=stala[a];
a+=base;
maks[a] = sum[a];
a/=2;
while (a>=1){
maks[a] = max(maks[a*2],maks[a*2+1])+sum[a];
a/=2;
}
}
map<int,int> tosmall;
int tobig[base];
vector<int> countScans(vector<int> a, vector<int> x, vector<int> v){
int n = a.size(), q = x.size();
vector<int> odp(q);
vector<int> move;
rep(n){
move.pb(a[i]);
}
rep(q){
move.pb(v[i]);
}
int c = -1;
int last = -2137;
sort(all(move));
for (int i : move){
if (i!=last){
last = i;
c++;
tobig[c] = i;
tosmall[i] = c;
}
}
rep(base){
pos[i].insert(-1e8);
}
rep(n){
a[i] = tosmall[a[i]];
pos[a[i]].insert(i);
dodaj(0,base-1,a[i]+1,base-1,1,-1);
}
rep(base){
auto it = pos[i].end();
it--;
ustaw(i,*it);
}
rep(q){
int old = a[x[i]];
int nowy = tosmall[v[i]];
pos[old].erase(x[i]);
pos[nowy].insert(x[i]);
dodaj(0,base-1,old+1,base-1,1,1);
dodaj(0,base-1,nowy+1,base-1,1,-1);
auto it = pos[old].end();
it--;
ustaw(old,*it);
auto it1 = pos[nowy].end();
it1--;
ustaw(nowy,*it1);
odp[i] = maks[1];
}
return odp;
}
/*int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,q;
cin >> n >> q;
vector<int> a(n);
vector<int> x(q);
vector<int> v(q);
rep(n) cin >> a[i];
rep(q) cin >> x[i] >> v[i];
vector<int> odp = countScans(a,x,v);
for (int i : odp) cout << i << '\n';
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
115620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
115620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
116928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
142 ms |
115620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
