This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/*input
8
1 1 1 1 1 1 2 1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e6 + 1099;
const int mod=1e9 + 7;
#define pii pair<int, int>
#define f first
#define s second
#define mp make_pair
int n;map<int, int> conv;
multiset<int> positions[N];
class tree
{
int tree[4*N], lazy[4*N], ql, qr, val;
void prop(int i, int l, int r)
{
tree[i]+=lazy[i];
if(l!=r)
{
lazy[2*i]+=lazy[i];lazy[2*i+1]+=lazy[i];
}
lazy[i]=0;
}
void update(int i=1, int l=1, int r=N-1)
{
prop(i, l, r);
if(l>qr||r<ql) return;
if(l>=ql&&r<=qr)
{
lazy[i]+=val;prop(i, l, r);
return;
}
int mid=(l+r)>>1;update(2*i, l, mid);update(2*i+1, mid+1, r);tree[i]=max(tree[2*i], tree[2*i+1]);
}
public:
void remove(int ind, int el)
{
int prevmax=(*positions[el].rbegin());
positions[el].erase(ind);
if(!positions[el].empty()) prevmax=(*positions[el].rbegin()) - prevmax;
else prevmax*=-1;
ql=qr=el;val=prevmax;
if(val!=0) update();
ql=el+1;qr=N-1;val=+1;
if(!positions[el].empty()) ql--;
update();
}
void add(int ind, int el)
{
int prevmax=0;
if(!positions[el].empty()) prevmax=(*positions[el].rbegin());
positions[el].insert(ind);
prevmax=(*positions[el].rbegin() - prevmax);
ql=qr=el;val=prevmax;
if(val!=0) update();
ql=el+1;qr=N-1;val=-1;
if(positions[el].size()>1) ql--;
update();
}
int qry()
{
return tree[1];
}
};
tree Segtree;
vector<int> countScans(vector<int> arr, vector<int> pos, vector<int> nval)
{
n=arr.size();int q=pos.size();vector<int> ans;
conv.clear();
for(auto i:arr) conv[i]=0;
for(auto i:nval) conv[i]=0;
int curv=1;
for(auto &i:conv) i.s=curv++;
for(int i=0;i<n;i++) {arr[i]=conv[arr[i]];Segtree.add(i, arr[i]);}
for(auto &i:nval) i=conv[i];
//cout<<Segtree.qry()<<endl;
for(int i=0;i<q;i++)
{
Segtree.remove(pos[i], arr[pos[i]]);
Segtree.add(pos[i], nval[i]);arr[pos[i]]=nval[i];
ans.push_back(Segtree.qry());
}
return ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |