Submission #256667

# Submission time Handle Problem Language Result Execution time Memory
256667 2020-08-03T06:11:02 Z daniel920712 Street Lamps (APIO19_street_lamps) C++14
0 / 100
89 ms 95636 KB
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <set>
#include <utility>

using namespace std;
set < pair < int , int > > how;
struct A
{
    int l,r;
    int nxl,nxr,nxt;
    int con;
}Node[2000005];
int now=1;
char temp[15];
char all[300005];
int con[105][105]={0};
int Find(int x,int y,int here)
{
    if(here==-1) return 0;
    int t;
    //printf("aa %d\n",Node[here].con);
    if(Node[here].nxt==-2)
    {
        t=Node[here].con;
        if(Node[here].l==y&&Node[here].r==y) return t;
        else if(y<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
        else t+=Find(x,y,Node[here].nxr);
    }
    else
    {
        t=Node[here].con;
        t+=Find(x,y,Node[here].nxt);
        if(Node[here].l==x&&Node[here].r==x) return t;
        else if(x<=(Node[here].l+Node[here].r)/2) t+=Find(x,y,Node[here].nxl);
        else t+=Find(x,y,Node[here].nxr);
    }
    //printf("%d %d %d %d\n",Node[here].l,Node[here].r,Node[here].nxt,t);
    return t;
}
void build(int l,int r,int con,int here)
{
    Node[here].l=l;
    Node[here].r=r;
    Node[here].nxt=con;
    Node[here].nxl=-1;
    Node[here].nxr=-1;
    Node[here].con=0;
}
void cha(int l1,int r1,int l2,int r2,int con,int here)
{
    int t;
    //printf("%d %d %d %d %d %d\n",l1,r1,l2,r2,here,Node[here].nxt);
    if(Node[here].nxt==-2)
    {
        //return ;
        if(Node[here].l==l2&&Node[here].r==r2)
        {
            Node[here].con+=con;
            return ;
        }
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            build(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl);
        }
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            build((Node[here].l+Node[here].r)/2+1,Node[here].r,-2,Node[here].nxr);
        }

        if(r2<=(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxl);
        else if(l2>(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxr);
        else
        {
            cha(l1,r1,l2,(Node[here].l+Node[here].r)/2,con,Node[here].nxl);
            cha(l1,r1,(Node[here].l+Node[here].r)/2+1,r2,con,Node[here].nxr);
        }
    }
    else
    {
        if(Node[here].nxt==-1)
        {
            Node[here].nxt=now++;
            build(0,300000,-2,Node[here].nxt);
        }
        if(Node[here].l==l1&&Node[here].r==r1)
        {
            cha(l1,r1,l2,r2,con,Node[here].nxt);
            return;
        }
        if(Node[here].nxl==-1)
        {
            Node[here].nxl=now++;
            build(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
        }
        if(Node[here].nxr==-1)
        {
            Node[here].nxr=now++;
            build((Node[here].l+Node[here].r)/2+1,Node[here].r,-1,Node[here].nxr);
        }
        if(r1<=(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxl);
        else if(l1>(Node[here].l+Node[here].r)/2) cha(l1,r1,l2,r2,con,Node[here].nxr);
        else
        {
            cha(l1,(Node[here].l+Node[here].r)/2,l2,r2,con,Node[here].nxl);
            cha((Node[here].l+Node[here].r)/2+1,r1,l2,r2,con,Node[here].nxr);
        }
    }
}
int main()
{
    int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
    scanf("%d %d",&N,&M);
    scanf("%s",all+1);
    build(0,300000,-1,0);
    l=1;
    r=0;
    for(i=1;i<=N;i++)
    {
        if(all[i]=='1') r=i;
        else
        {
            if(r>=l)
            {
                how.insert(make_pair(l,r));
                cha(l,r+1,l,r+1,M,0);
            }

            l=i+1;
            r=i;
        }
    }
    if(r>=l)
    {
        how.insert(make_pair(l,r));
        cha(l,r+1,l,r+1,M,0);
    }
    for(i=1;i<=M;i++)
    {
        scanf("%s",temp);
        if(temp[0]=='t')
        {
            scanf("%d",&where);
            if(all[where]=='0')
            {
                auto a=how.lower_bound(make_pair(where,where));
                auto b=prev(a);
                r1=where;
                l2=where+1;

                if(a==how.end()||all[where+1]=='0') r2=where+1;
                else r2=a->second+1;

                if(a==how.begin()||all[where-1]=='0') l1=where;
                else l1=b->first;

                if(r2!=where+1) how.erase(a);
                if(l1!=where) how.erase(b);

                if(r2-1>=l1) how.insert(make_pair(l1,r2-1));

                //printf("bb %d %d %d %d\n",l1,r1,l2,r2);
                //for(auto i:how) printf("aa %d %d\n",i.first,i.second);
                cha(l1,r1,l2,r2,M-i,0);
            }
            else
            {
                auto a=prev(how.upper_bound(make_pair(where,where)));
                l1=a->first;
                r1=where;
                l2=where+1;
                r2=a->second+1;
                //printf("cc %d %d\n",a->first,a->second);
                how.erase(a);
                if(r1-1>=l1) how.insert(make_pair(l1,r1-1));
                if(r2-1>=l2) how.insert(make_pair(l2,r2-1));

                //printf("cc %d %d %d %d\n",l1,r1,l2,r2);
                //for(auto i:how) printf("aa %d %d\n",i.first,i.second);
                //printf("%d %d %d %d\n",l1,r1,l2,r2);
                cha(l1,r1,l2,r2,i-M,0);
            }
            all[where]=(1-(all[where]-'0'))+'0';
        }
        else
        {
            scanf("%d %d",&l,&r);
            ok=1;
            if(how.find(make_pair(l,r-1))!=how.end()) ok=0;
            printf("%d\n",max(Find(l,r,0)-(M-i)*ok,0));
        }
    }
    return 0;
}

Compilation message

street_lamps.cpp: In function 'void cha(int, int, int, int, int, int)':
street_lamps.cpp:53:9: warning: unused variable 't' [-Wunused-variable]
     int t;
         ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:115:13: warning: unused variable 't' [-Wunused-variable]
     int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
             ^
street_lamps.cpp:115:33: warning: unused variable 'j' [-Wunused-variable]
     int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                 ^
street_lamps.cpp:115:35: warning: unused variable 'k' [-Wunused-variable]
     int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                   ^
street_lamps.cpp:115:43: warning: unused variable 'ok1' [-Wunused-variable]
     int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                           ^~~
street_lamps.cpp:115:49: warning: unused variable 'ok2' [-Wunused-variable]
     int N,M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                                 ^~~
street_lamps.cpp:116:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&N,&M);
     ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s",all+1);
     ~~~~~^~~~~~~~~~~~
street_lamps.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",temp);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:146:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&where);
             ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:190:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 86 ms 95636 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 89 ms 95584 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -