Submission #347924

#	Time	Username	Problem	Language	Result	Execution time	Memory
347924		denkendoemeer	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	4094 ms	65092 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;
struct nr
{
    bool ok;
    int st,dr,x,del;
}a[1500005],b[1500005];
int ans[1500005];
int cmp(nr a,nr b)
{
    return a.x<b.x;
}
void update(int st,int dr)
{
    if (dr==st+1)
        return ;
    int mij=(st+dr)/2;
    update(st,mij);
    update(mij,dr);
    int i;
    for(i=st;i<dr;i++)
        b[i].dr=(i<mij);
    inplace_merge(b+st,b+mij,b+dr,cmp);
    int sum=0;
    for(i=st;i<dr;i++){
        if (b[i].ok==0 && b[i].st && b[i].dr)
            sum=sum+b[i].del*b[i].x;
        if (b[i].ok && b[i].st==0 && b[i].dr==0)
            ans[b[i].x]+=sum;
    }
}
int cmp2(nr a,nr b)
{
    return make_pair(-a.dr,a.ok)<make_pair(-b.dr,b.ok);
}
void update2(int st,int dr)
{
    if (dr==st+1)
        return ;
    int mij=(st+dr)/2;
    update2(st,mij);
    update2(mij,dr);
    int i;
    for(i=st;i<dr;i++)
        a[i].st=(i<mij);
    merge(a+st,a+mij,a+mij,a+dr,b+st,cmp2);
    for(i=st;i<dr;i++)
        a[i]=b[i];
    update(st,dr);
}
set<int>st;
int cmp3(nr a,nr b)
{
    return make_pair(a.st,a.ok)<make_pair(b.st,b.ok);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int n,q,u=0,i;
    char ch;
    scanf("%d%d\n",&n,&q);
    int last=-1;
    st.insert(-1);
    for(i=0;i<n;i++){
        ch=getchar();
        if (ch!='0')
            if (u && a[u-1].dr==i)
                a[u-1].dr=i+1;
            else
                a[u++]=(nr){0,last+1,i+1,-1,-1};
        else
            last=i,st.insert(i);
    }
    scanf("\n");
    st.insert(n);
    string s;
    int num;
    for(i=0;i<q;i++){
        cin>>s;
        if (s=="toggle"){
            int poz;
            scanf("%d\n",&poz);
            poz--;
            auto auxi=st.insert(poz);
            auto it=auxi.first;
            auto it2=auxi.second;
            if (it2)
                num=1;
            else
                num=-1;
            a[u++]=(nr){0,*prev(it)+1,*next(it),i,+num};
            a[u++]=(nr){0,*prev(it)+1,poz,i,-num};
            a[u++]=(nr){0,poz+1,*next(it),i,-num};
            if (num==-1)
                st.erase(it);
            ans[i]=-1;
        }
        else{
            int x,y;
            scanf("%d%d\n",&x,&y);
            x--;
            y--;
            a[u++]={1,x,y,i,0};
            if (*st.lower_bound(x)<y)
                ans[i]=0;
            else
                ans[i]=i;
        }
    }
    sort(a,a+u,cmp3);
    update2(0,u);
    for(i=0;i<q;i++)
        if (ans[i]>=0)
            printf("%d\n",ans[i]);
return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |     scanf("%d%d\n",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |     scanf("\n");
      |     ~~~~~^~~~~~
street_lamps.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |             scanf("%d\n",&poz);
      |             ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:101:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  101 |             scanf("%d%d\n",&x,&y);
      |             ~~~~~^~~~~~~~~~~~~~~~

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