#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], as[maxn], vs[maxn], n, q;
ii 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 type){
if(l>x||r<x)return;
if(l==r){
if(type==-inf)freq[i] = {0,-inf};
else freq[i] = {1,type};
return;
}
int md = (l+r)/2;
updatef(2*i,l,md,x,type), updatef(2*i+1,md+1,r,x,type);
freq[i].first = freq[2*i].first + freq[2*i+1].first, freq[i].second = max(freq[2*i].second,freq[2*i+1].second);
}
int query(int i,int l,int r,int x){
if(l==r){
return freq[i].second<=x;
}
int md = (l+r)/2;
if(freq[2*i].second<=x)return freq[2*i].first + query(2*i+1,md+1,r,x);
return query(2*i,l,md,x);
}
void adiciona(int i,int l,int r,int x,int d){
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 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 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,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)as[v2[i].second-1] = v2[i].first, a[v2[i].second-1] = i;
else vs[v2[i].second-1-n] = v2[i].first, v[v2[i].second-1-n] = i;
}
for(int i=0;i<n;++i){
updatef(1,1,n+q,a[i],as[i]);
}
for(int i=0;i<n;++i){
int precisa = max(0,i - query(1,1,n+q,as[i])+1);
// cout<<query(1,1,n+q,as[i])<<" \n"[i==n-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,-inf), adiciona(1,1,n+q,atual,-6e5), updatef(1,1,n+q,novo,vs[i]);
int precisa = max(0,x[i] - query(1,1,n+q,vs[i])+1);
if(atual<novo)update(1,1,n+q,atual,novo,1);
if(atual>novo)update(1,1,n+q,novo,atual,-1);
adiciona(1,1,n+q,novo,precisa);
answers.pb(max(0,seg[1]));
a[x[i]] = novo;
}
return answers;
}
// 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 |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
2760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
