#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ii = pair<int,int>;
using iii = tuple<int,int,int>;
const int inf = 2e9+1;
const int mod = 1e9+7;
const int maxn = 1e6+100;
template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }
int val[maxn], seg[4*maxn], lazy[4*maxn], n, q, freq[4*maxn];
vector<ii>v2 = {{-inf,0}};
//comprimir coordenadas de todos os valores (iniciais e alteracoes nas queries)
//necessario pra ordenar: max(0,posicao atual - posicao ordenada)
//pra achar posicao ordenada: seg de frequencia com compressao
//update: vou trocar x por y
//se x < y, todo mundo entre compressao(x) e compressao(y) diminui em 1.
//se x > y, todo mundo entre compressao(x) e compressao(y) aumenta em 1.
//se x=y, fodase
void updatef(int i,int l,int r,int x,int d){
if(l>x||r<x)return;
if(l==r){
freq[i] = d;
return;
}
int md = (l+r)/2;
updatef(2*i,l,md,x,d), updatef(2*i+1,md+1,r,x,d);
freq[i] = freq[2*i] + freq[2*i+1];
}
int query(int i,int l,int r,int x){
if(!x)return 0;
if(l==r)return freq[i];
int md = (l+r)/2;
if(md<x)return freq[2*i] + query(2*i+1,md+1,r,x);
return query(2*i,l,md,x);
}
void push(int i,int l,int r){
seg[i] += lazy[i];
if(l!=r)lazy[2*i] += lazy[i], lazy[2*i+1] += lazy[i];
lazy[i] = 0;
}
void adiciona(int i,int l,int r,int x,int d){
push(i,l,r);
if(l>x||r<x)return;
if(l==r){
seg[i] = d;
return;
}
int md = (l+r)/2;
adiciona(2*i,l,md,x,d), adiciona(2*i+1,md+1,r,x,d);
seg[i] = max(seg[2*i],seg[2*i+1]);
}
void update(int i,int l,int r,int x,int y,int d){
push(i,l,r);
if(l>y||r<x)return;
if(x<=l&&r<=y){
lazy[i] += d;
push(i,l,r);
return;
}
int md = (l+r)/2;
update(2*i,l,md,x,y,d), update(2*i+1,md+1,r,x,y,d);
seg[i] = max(seg[2*i],seg[2*i+1]);
}
vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
q=sz(x), n=sz(a);
vector<int>answers;
for(int i=1;i<=4*(n+q);++i)seg[i] = -6e5, freq[i] = 0;
for(int i=0;i<n;++i){
v2.pb({a[i],i+1});
}
for(int i=0;i<q;++i){
v2.pb({v[i],n+1+i});
}
sort(all(v2));
for(int i=1;i<=n+q;++i){
if(v2[i].second<=n)a[v2[i].second-1] = i;
else v[v2[i].second-1-n] = i;
}
for(int i=0;i<n;++i){
updatef(1,1,n+q,a[i],1);
}
for(int i=0;i<n;++i){
int precisa = max(0,i - query(1,1,n+q,a[i]-1));
adiciona(1,1,n+q,a[i],precisa);
}
for(int i=0;i<q;++i){
int atual = a[x[i]], novo = v[i];
updatef(1,1,n+q,atual,0), adiciona(1,1,n+q,atual,-6e5), updatef(1,1,n+q,novo,1);
int precisa = max(0,x[i] - query(1,1,n+q,a[i]-1));
update(1,1,n+q,atual+1,n+q,1);
update(1,1,n+q,novo+1,n+q,-1);
adiciona(1,1,n+q,novo,precisa);
push(1,1,n+q);
answers.pb(max(0,seg[1]));
a[x[i]] = novo;
}
return answers;
}
//5 4 3 2 5
//4 3 2 5 5
//3 2 4 5 5
// int main(){
// int n,q;cin>>n>>q;
// vector<int>a;
// for(int i=1;i<=n;++i){
// int x;cin>>x;
// a.pb(x);
// }
// vector<int>x,v;
// for(int i=0;i<q;++i){
// int d,f;cin>>d>>f;
// x.pb(d), v.pb(f);
// }
// vector<int>resp = countScans(a,x,v);
// for(auto x:resp)cout<<x<<" ";
// }
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
22 ms |
2128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
