oj.uz

Submission #257875

# Submission time Handle Problem Language Result Execution time Memory
257875 2020-08-04T23:23:41 Z daniel920712 Street Lamps (APIO19_street_lamps) C++14
100 / 100
 1089 ms 229500 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[80000005];
int now=1;
char temp[15];
char all[300005];
int N;
int Find(int x,int y,int here)
{
    if(here<0) return 0;
    int t;
    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);
    }
    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;
    if(Node[here].nxt==-2)
    {
        if(Node[here].l==l2&&Node[here].r==r2)
        {
            Node[here].con+=con;
            return ;
        }
        if(r2<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                build(Node[here].l,(Node[here].l+Node[here].r)/2,-2,Node[here].nxl);
            }
            cha(l1,r1,l2,r2,con,Node[here].nxl);
        }
        else if(l2>(Node[here].l+Node[here].r)/2)
        {
            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);
            }
            cha(l1,r1,l2,r2,con,Node[here].nxr);
        }
        else
        {
            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);
            }
            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].l==l1&&Node[here].r==r1)
        {
            if(Node[here].nxt==-1)
            {
                Node[here].nxt=now++;
                build(0,N+1,-2,Node[here].nxt);
            }
            cha(l1,r1,l2,r2,con,Node[here].nxt);
            return;
        }
        if(r1<=(Node[here].l+Node[here].r)/2)
        {
            if(Node[here].nxl==-1)
            {
                Node[here].nxl=now++;
                build(Node[here].l,(Node[here].l+Node[here].r)/2,-1,Node[here].nxl);
            }
            cha(l1,r1,l2,r2,con,Node[here].nxl);
        }
        else if(l1>(Node[here].l+Node[here].r)/2)
        {
            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);
            }
            cha(l1,r1,l2,r2,con,Node[here].nxr);
        }
        else
        {
            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);
            }
            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()
{
    //freopen("17","rt",stdin);
    int 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,N+1,-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')
            {
                if(how.empty())
                {
                    cha(where,where,where+1,where+1,M-i,0);
                    how.insert(make_pair(where,where));
                    all[where]=(1-(all[where]-'0'))+'0';
                    continue;
                }
                auto a=how.lower_bound(make_pair(where+1,where));
                auto b=prev(a);
                //printf("aa\n");
                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("%d %d %d %d\n",l1,r1,l2,r2);
                cha(l1,r1,l2,r2,M-i,0);
            }
            else
            {
                auto a=prev(how.lower_bound(make_pair(where+1,where)));
                l1=a->first;
                r1=where;
                l2=where+1;
                r2=a->second+1;
                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));
                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.lower_bound(make_pair(l+1,r))!=how.begin()&&prev(how.lower_bound(make_pair(l+1,r)))->first<=l&&prev(how.lower_bound(make_pair(l+1,r)))->second>=r-1) ok=1;
            else 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:51:9: warning: unused variable 't' [-Wunused-variable]
     int t;
         ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:143:11: warning: unused variable 't' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
           ^
street_lamps.cpp:143:31: warning: unused variable 'j' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                               ^
street_lamps.cpp:143:33: warning: unused variable 'k' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                 ^
street_lamps.cpp:143:41: warning: unused variable 'ok1' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                         ^~~
street_lamps.cpp:143:47: warning: unused variable 'ok2' [-Wunused-variable]
     int M,t,l,r,l1,r1,l2,r2,i,j,k,where,ok1=0,ok2=0,ok;
                                               ^~~
street_lamps.cpp:144: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:145: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:171:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",temp);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&where);
             ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:215:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d %d",&l,&r);
             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 4620 KB Output is correct
2 Correct 276 ms 5112 KB Output is correct
3 Correct 402 ms 10264 KB Output is correct
4 Correct 912 ms 136932 KB Output is correct
5 Correct 1089 ms 185080 KB Output is correct
6 Correct 897 ms 144728 KB Output is correct
7 Correct 155 ms 7160 KB Output is correct
8 Correct 181 ms 8568 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 896 KB Output is correct
2 Correct 3 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1079 ms 229500 KB Output is correct
6 Correct 1066 ms 217720 KB Output is correct
7 Correct 1010 ms 184440 KB Output is correct
8 Correct 180 ms 8568 KB Output is correct
9 Correct 129 ms 4088 KB Output is correct
10 Correct 139 ms 4344 KB Output is correct
11 Correct 141 ms 4604 KB Output is correct
12 Correct 152 ms 7160 KB Output is correct
13 Correct 182 ms 8568 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 2 ms 640 KB Output is correct
3 Correct 2 ms 640 KB Output is correct
4 Correct 2 ms 768 KB Output is correct
5 Correct 750 ms 93292 KB Output is correct
6 Correct 796 ms 119728 KB Output is correct
7 Correct 842 ms 144248 KB Output is correct
8 Correct 957 ms 170188 KB Output is correct
9 Correct 239 ms 4344 KB Output is correct
10 Correct 192 ms 3324 KB Output is correct
11 Correct 231 ms 4344 KB Output is correct
12 Correct 196 ms 3320 KB Output is correct
13 Correct 235 ms 4344 KB Output is correct
14 Correct 194 ms 3320 KB Output is correct
15 Correct 157 ms 7160 KB Output is correct
16 Correct 182 ms 8636 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 232 ms 4620 KB Output is correct
9 Correct 276 ms 5112 KB Output is correct
10 Correct 402 ms 10264 KB Output is correct
11 Correct 912 ms 136932 KB Output is correct
12 Correct 1089 ms 185080 KB Output is correct
13 Correct 897 ms 144728 KB Output is correct
14 Correct 155 ms 7160 KB Output is correct
15 Correct 181 ms 8568 KB Output is correct
16 Correct 2 ms 896 KB Output is correct
17 Correct 3 ms 768 KB Output is correct
18 Correct 3 ms 768 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1079 ms 229500 KB Output is correct
21 Correct 1066 ms 217720 KB Output is correct
22 Correct 1010 ms 184440 KB Output is correct
23 Correct 180 ms 8568 KB Output is correct
24 Correct 129 ms 4088 KB Output is correct
25 Correct 139 ms 4344 KB Output is correct
26 Correct 141 ms 4604 KB Output is correct
27 Correct 152 ms 7160 KB Output is correct
28 Correct 182 ms 8568 KB Output is correct
29 Correct 2 ms 640 KB Output is correct
30 Correct 2 ms 640 KB Output is correct
31 Correct 2 ms 640 KB Output is correct
32 Correct 2 ms 768 KB Output is correct
33 Correct 750 ms 93292 KB Output is correct
34 Correct 796 ms 119728 KB Output is correct
35 Correct 842 ms 144248 KB Output is correct
36 Correct 957 ms 170188 KB Output is correct
37 Correct 239 ms 4344 KB Output is correct
38 Correct 192 ms 3324 KB Output is correct
39 Correct 231 ms 4344 KB Output is correct
40 Correct 196 ms 3320 KB Output is correct
41 Correct 235 ms 4344 KB Output is correct
42 Correct 194 ms 3320 KB Output is correct
43 Correct 157 ms 7160 KB Output is correct
44 Correct 182 ms 8636 KB Output is correct
45 Correct 105 ms 2824 KB Output is correct
46 Correct 145 ms 2808 KB Output is correct
47 Correct 463 ms 56056 KB Output is correct
48 Correct 910 ms 136500 KB Output is correct
49 Correct 152 ms 4472 KB Output is correct
50 Correct 151 ms 4476 KB Output is correct
51 Correct 155 ms 4600 KB Output is correct
52 Correct 159 ms 5112 KB Output is correct
53 Correct 155 ms 4984 KB Output is correct
54 Correct 159 ms 5056 KB Output is correct