Submission #405143

#	Time	Username	Problem	Language	Result	Execution time	Memory
405143		A_D	가로등 (APIO19_street_lamps)	C++14	20 / 100	1815 ms	118108 KiB

street_lamps

#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];
map<ii,int> ans;
map<int,int> l;
map<int,int> r;
set<int> st[N];
string qu[N];
int a[N];
int b[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);
        }
        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 solve()
{
    int n,q;
    cin>>n>>q;
    n++;
    string s;
    cin>>s;
    for(int i=1;i<=n;i++)st[i].insert(1e8);
    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'){
            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];
        }
    }
    //cout<<5<<endl;
    for(int i=1;i<=q;i++){
        if(qu[i]=="query"){
            if(ans.count({a[i],b[i]})==0){
                printf("0\n");
            }
            else{
      //          cout<<ans[{a[i],b[i]}]<<" ";
                int u=i-ans[{a[i],b[i]}];
                printf("%lld\n",u);
            }
        }
        else{
            int j=a[i];
            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];
        }
    }
}

main()
{
    int t=1;
    //cin>>t;
    while(t--)solve();
}

Compilation message (stderr)

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20