Submission #405170

#	Time	Username	Problem	Language	Result	Execution time	Memory
405170		A_D	Bridges (APIO19_bridges)	C++14	0 / 100	168 ms	104076 KiB

bridges

#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)
{
    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}]=v-ans[{s,u}];
            st[s].insert(u);
            st2[s].erase(u);
        }
        seg[p]=*st2[s].rbegin();
        return;
    }
    int mid=(s+e)/2;
    update2(p*2,s,mid,l1,r1,l2,r2,v);
    update2(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();
}

Compilation message (stderr)

bridges.cpp:136:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  136 | main()
      | ^~~~
bridges.cpp: In function 'void solve()':
bridges.cpp:85:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |             scanf("%lld",&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:86:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |             scanf("%lld",&b[i]);
      |             ~~~~~^~~~~~~~~~~~~~
bridges.cpp:90:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |             scanf("%lld",&a[i]);
      |             ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27