| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 405167 | A_D | Bridges (APIO19_bridges) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define F first
#define S second
#define du long double
using namespace std;
const int N=3e5+100;
int seg[4*N];
int seg2[4*N];
map<ii,int> ans;
map<ii,int> ann;
map<int,int> l;
map<int,int> r;
set<int> st[N];
set<int> st2[N];
string qu[N];
int a[N];
int b[N];
bool vis[N];
void build(int p,int s,int e)
{
if(s==e){
seg[p]=*st[s].begin();
return;
}
int mid=(s+e)/2;
build(p*2,s,mid);
build(p*2+1,mid+1,e);
seg[p]=min(seg[p*2],seg[p*2+1]);
}
void update(int p,int s,int e,int l1,int r1,int l2,int r2,int v)
{
if(s>r1||e<l1||seg[p]>r2){
return;
}
if(s==e){
while(1){
int u=*st[s].lower_bound(l2);
if(u>r2)break;
ans[{s,u}]=v;
st[s].erase(u);
st2[s].insert(u);
}
seg[p]=*st[s].begin();
return;
}
int mid=(s+e)/2;
update(p*2,s,mid,l1,r1,l2,r2,v);
update(p*2+1,mid+1,e,l1,r1,l2,r2,v);
seg[p]=min(seg[p*2],seg[p*2+1]);
}
void update2(int p,int s,int e,int l1,int r1,int l2,int r2,int v,int i)
{
if(s>r1||e<l1||seg[p]<l2){
return;
}
if(s==e){
while(1){
int u=*st2[s].rbegin();
if(u<l2)break;
ann[{s,u}]=i-ans[{s,u}];
st[s].insert(u);
st2[s].erase(u);
}
seg[p]=*st2[s].rbegin();
return;
}
int mid=(s+e)/2;
update(p*2,s,mid,l1,r1,l2,r2,v);
update(p*2+1,mid+1,e,l1,r1,l2,r2,v);
seg[p]=max(seg[p*2],seg[p*2+1]);
}
void solve()
{
int n,q;
cin>>n>>q;
n++;
string s;
cin>>s;
for(int i=1;i<=n;i++)st[i].insert(1e8),st2[i].insert(0);
for(int i=1;i<=q;i++){
cin>>qu[i];
if(qu[i]=="query"){
scanf("%lld",&a[i]);
scanf("%lld",&b[i]);
st[a[i]].insert(b[i]);
}
else{
scanf("%lld",&a[i]);
}
}
build(1,1,n);
for(int i=1;i<=n;i++){
l[i]=i;
r[i]=i;
}
for(int i=1;i<n;i++){
if(s[i-1]=='1'){
vis[i]=1;
update(1,1,n,l[i],r[i],l[i+1],r[i+1],0);
r[l[i]]=r[i+1];
l[r[i+1]]=l[i];
}
}
for(int i=1;i<=q;i++){
if(qu[i]=="query"){
if(ans.count({a[i],b[i]})==0){
printf("0\n");
}
else{
int u=i-ans[{a[i],b[i]}]+ann[{a[i],b[i]}];
printf("%lld\n",u);
}
}
else{
int j=a[i];
if(vis[j]==0){
update(1,1,n,l[j],r[j],l[j+1],r[j+1],i);
r[l[j]]=r[j+1];
l[r[j+1]]=l[j];
vis[j]=1;
}
else{
int ll=l[j];
l[r[ll]]=j+1;
r[j+1]=r[ll];
r[ll]=j;
update2(1,1,n,l[j],r[j],l[j+1],r[j+1],i);
vis[j]=0;
}
}
}
}
main()
{
int t=1;
//cin>>t;
while(t--)solve();
}