#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define N 500005
using namespace std;
ll n,m,pown=1,a[N],b[N],c[N],t[10*N],save[10*N],l,r,ad;
vector<ll>v;
map<ll,ll>mp;
set<ll>st[3 * N];
void updd(ll x){
if(!x)return;
t[x] = max(t[2 * x] , t[2 * x + 1]);
updd(x / 2);
}
void upd(ll x,ll L,ll R){
if(L > r || R < l)return;
if(L >= l && R <= r){
save[x] += ad;
t[x] += ad;
return;
}
if(save[x]){
save[2 * x] += save[x];
save[2 * x + 1] += save[x];
t[2 * x] += save[x];
t[2 * x + 1] += save[x];
save[x] = 0;
}
upd(2 * x, L , (L + R) / 2);
upd(2 * x + 1 , (L + R) / 2 + 1, R);
t[x] = max(t[2 * x] , t[2 * x + 1]);
}
vector<int> countScans(vector<int>ff ,vector<int>uu,vector<int>vv){
n = ff.size();
m = uu.size();
for(int i=1; i<=n; i++)
a[i] = ff[i - 1],
v.pb(a[i]);
for(int i=1; i<=n; i++){
b[i] = uu[i - 1] + 1;
c[i] = vv[i - 1];
v.pb(c[i]);
}
sort(v.begin() , v.end());
ll p = 0;
for(int i=0; i<v.size(); i++){
if(!i || v[i] != v[i - 1])p++;
mp[v[i]] = p;
}
for(int i=1; i<=n; i++){
a[i] = mp[a[i]];
st[a[i]].insert(-i);
}
for(int i=1; i<=m; i++)
c[i] = mp[c[i]];
while(pown <= n + m)
pown *= 2;
for(int i=1; i<=n; i++){
t[pown + i - 1] = -(*st[a[i]].begin());
save[pown + i - 1] = -(*st[a[i]].begin());
l = a[i],r = n + m;
ad = -1;
upd(1 , 1 , pown);
updd((pown + i - 1) / 2);
}
vector<int>ans;
for(int q=1; q<=m; q++){
ll x,y;
x = b[q];
y = c[q];
l = a[x],r = a[x];
ad = (*st[a[x]].begin());
st[a[x]].erase(st[a[x]].find(-x));
if(st[a[x]].size())ad -= (*st[a[x]].begin());
upd(1 , 1 , pown);
ad = 1;
l = a[x],r = n + m;
upd(1 , 1 , pown);
a[x] = y;
l = a[x],r = a[x];
ad = (*st[a[x]].begin());
st[a[x]].insert(-x);
ad -= (*st[a[x]].begin());
upd(1 , 1 , pown);
ad = -1;
l = a[x] , r = n + m;
upd(1 , 1 , pown);
ans.pb(t[1]);
//cout << t[1] << " ";
}
return ans;
}
/*
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
vector<ll>aa,xx,yy;
for(int i=1; i<=n; i++){
ll x;
cin >> x;
aa.pb(x);
}
for(int i=1; i<=m; i++){
ll x,y;
cin >> x >> y;
xx.pb(x);
yy.pb(y);
}
countScans(aa , xx , yy);
return 0;
}
*/
Compilation message
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<v.size(); i++){
~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9090 ms |
71160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9090 ms |
71160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
96 ms |
74420 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
9090 ms |
71160 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
