Submission #257686

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
257686	2020-08-04T14:39:57 Z	trttrttrt	Street Lamps (APIO19_street_lamps)	C++17	Compilation error	0 ms	0 KB

street_lamps

using namespace std;
inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}

int n,m;
char s[N];
struct interval {
    int lp,rp;
    int l,r;
    interval() {}
    interval(int _lp,int _rp,int _l,int _r) {lp=_lp,rp=_rp,l=_l,r=_r;}
    bool operator <(const interval &a)const {return rp<a.rp;}
}t[N<<2];

set<int>pos;
set<int>::iterator it;
int id[N],R[N];
int tot;
int ans[N];

struct query {
    int l,r,tim,id;
}q[N];

int qt;
struct node {
    int op,id,r;
    node() {}
    node(int _op,int _id,int _r) {
        op=_op,id=_id,r=_r;
    }
};

bool cmpr(const node &a,const node &b) {
    if(a.r!=b.r) return a.r>b.r;
    return a.op<b.op;
}

bool cmpl(const node &a,const node &b) {
    if(a.op!=b.op) return a.op<b.op;
    if(a.op==1) return t[a.id].lp<t[b.id].lp;
    else return q[a.id].l<q[b.id].l;
}

node st[N<<2];
int top;

struct tree {
    int l,r;
    int sum,tag;
}tr[N<<2];

void update(int v) {tr[v].sum=tr[v<<1].sum+tr[v<<1|1].sum;}
void Add(int v,int f) {tr[v].sum+=(tr[v].r-tr[v].l+1)*f,tr[v].tag+=f;}
void down(int v) {
    if(tr[v].tag) {
        Add(v<<1,tr[v].tag);
        Add(v<<1|1,tr[v].tag);
        tr[v].tag=0;
    }
}
void build(int v,int l,int r) {
    tr[v].l=l,tr[v].r=r;
    if(l==r) return ;
    int mid=l+r>>1;
    build(v<<1,l,mid),build(v<<1|1,mid+1,r);
}

void Modify(int v,int l,int r,int f) {
    if(tr[v].l>r||tr[v].r<l) return ;
    if(l<=tr[v].l&&tr[v].r<=r) {
        Add(v,f);
        return ;
    }
    down(v);
    Modify(v<<1,l,r,f),Modify(v<<1|1,l,r,f);
    update(v);
}

int query(int v,int l,int r) {
    if(tr[v].l>r||tr[v].r<l) return 0;
    if(l<=tr[v].l&&tr[v].r<=r) return tr[v].sum;
    down(v);
    return query(v<<1,l,r)+query(v<<1|1,l,r);
}

void solve(int l,int r) {
    if(l==r) return ;
    int mid=l+r>>1;
    solve(l,mid),solve(mid+1,r);
    int tag=l;
    for(int i=mid+1;i<=r;i++) {
        if(st[i].op==1) continue ;
        while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
            Modify(1,t[st[tag].id].l,t[st[tag].id].r,1);
            tag++;
        }
        ans[st[i].id]+=query(1,1,q[st[i].id].tim);
    }
    for(int i=l;i<tag;i++) Modify(1,t[st[i].id].l,t[st[i].id].r,-1);
    inplace_merge(st+l,st+mid+1,st+r+1,cmpl);
}

int main() {
    n=Get(),m=Get();
    scanf("%s",s+1);
    char op[20];
    build(1,1,m);
    for(int i=1;i<=n;i++) {
        if(s[i]=='0') continue ;
        int j;
        for(j=i;j<=n&&s[j]=='1';j++);
        j--;
        R[i]=j;
        pos.insert(i);
        t[id[i]=++tot]=interval(i,j,1,m);
        i=j;
    }
    
    for(int i=1;i<=m;i++) {
        scanf("%s",op+1);
        int x;
        if(op[1]=='t') {
            x=Get();
            if(i==m) continue ;
            s[x]^=1;
            if(s[x]=='0') {
                it=pos.upper_bound(x);it--;
                int LL=*it,RR=R[LL];
                t[id[LL]].r=i;
                if(LL<x) {
                    t[id[LL]=++tot]=interval(LL,x-1,i+1,m);
                    R[LL]=x-1;
                } else pos.erase(LL);
                if(x<RR) {
                    t[id[x+1]=++tot]=interval(x+1,RR,i+1,m);
                    R[x+1]=RR;
                    pos.insert(x+1);
                }
            } else {
                int nowl=x,nowr=x;
                it=pos.upper_bound(x);
                if(it!=pos.end()) {
                    int y=*it;
                    if(y==x+1) {
                        nowr=R[y];
                        t[id[y]].r=i;
                        pos.erase(y);
                    }
                }
                it=pos.lower_bound(x);
                if(it!=pos.begin()) {
                    int y=*(--it);
                    if(R[y]==x-1) {
                        nowl=y;
                        t[id[y]].r=i;
                        pos.erase(y);
                    }
                }
                t[id[nowl]=++tot]=interval(nowl,nowr,i+1,m);
                R[nowl]=nowr;
                pos.insert(nowl);
            }
        } else {
            q[++qt].l=Get(),q[qt].r=Get()-1;
            q[qt].id=qt,q[qt].tim=i;
        }
    }
    for(int i=1;i<=tot;i++) {
        st[++top]=node(1,i,t[i].rp);
    }
    for(int i=1;i<=qt;i++) {
        st[++top]=node(2,i,q[i].r);
    }
    sort(st+1,st+1+top,cmpr);
    solve(1,top);
    for(int i=1;i<=qt;i++) cout<<ans[i]<<"\n";
    return 0;
}

Compilation message

street_lamps.cpp: In function 'int Get()':
street_lamps.cpp:2:39: error: 'getchar' was not declared in this scope
 inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
                                       ^~~~~~~
street_lamps.cpp:2:39: note: suggested alternative: 'char'
 inline int Get() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}while('0'<=ch&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;}
                                       ^~~~~~~
                                       char
street_lamps.cpp: At global scope:
street_lamps.cpp:5:8: error: 'N' was not declared in this scope
 char s[N];
        ^
street_lamps.cpp:12:4: error: 'N' was not declared in this scope
 }t[N<<2];
    ^
street_lamps.cpp:14:1: error: 'set' does not name a type; did you mean 'Get'?
 set<int>pos;
 ^~~
 Get
street_lamps.cpp:15:1: error: 'set' does not name a type; did you mean 'Get'?
 set<int>::iterator it;
 ^~~
 Get
street_lamps.cpp:16:8: error: 'N' was not declared in this scope
 int id[N],R[N];
        ^
street_lamps.cpp:16:13: error: 'N' was not declared in this scope
 int id[N],R[N];
             ^
street_lamps.cpp:18:9: error: 'N' was not declared in this scope
 int ans[N];
         ^
street_lamps.cpp:22:4: error: 'N' was not declared in this scope
 }q[N];
    ^
street_lamps.cpp: In function 'bool cmpl(const node&, const node&)':
street_lamps.cpp:40:24: error: 't' was not declared in this scope
     if(a.op==1) return t[a.id].lp<t[b.id].lp;
                        ^
street_lamps.cpp:41:17: error: 'q' was not declared in this scope
     else return q[a.id].l<q[b.id].l;
                 ^
street_lamps.cpp: At global scope:
street_lamps.cpp:44:9: error: 'N' was not declared in this scope
 node st[N<<2];
         ^
street_lamps.cpp:50:5: error: 'N' was not declared in this scope
 }tr[N<<2];
     ^
street_lamps.cpp: In function 'void update(int)':
street_lamps.cpp:52:21: error: 'tr' was not declared in this scope
 void update(int v) {tr[v].sum=tr[v<<1].sum+tr[v<<1|1].sum;}
                     ^~
street_lamps.cpp: In function 'void Add(int, int)':
street_lamps.cpp:53:24: error: 'tr' was not declared in this scope
 void Add(int v,int f) {tr[v].sum+=(tr[v].r-tr[v].l+1)*f,tr[v].tag+=f;}
                        ^~
street_lamps.cpp: In function 'void down(int)':
street_lamps.cpp:55:8: error: 'tr' was not declared in this scope
     if(tr[v].tag) {
        ^~
street_lamps.cpp: In function 'void build(int, int, int)':
street_lamps.cpp:62:5: error: 'tr' was not declared in this scope
     tr[v].l=l,tr[v].r=r;
     ^~
street_lamps.cpp:62:5: note: suggested alternative: 'r'
     tr[v].l=l,tr[v].r=r;
     ^~
     r
street_lamps.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~
street_lamps.cpp: In function 'void Modify(int, int, int, int)':
street_lamps.cpp:69:8: error: 'tr' was not declared in this scope
     if(tr[v].l>r||tr[v].r<l) return ;
        ^~
street_lamps.cpp:69:8: note: suggested alternative: 'r'
     if(tr[v].l>r||tr[v].r<l) return ;
        ^~
        r
street_lamps.cpp:70:11: error: 'tr' was not declared in this scope
     if(l<=tr[v].l&&tr[v].r<=r) {
           ^~
street_lamps.cpp:70:11: note: suggested alternative: 'r'
     if(l<=tr[v].l&&tr[v].r<=r) {
           ^~
           r
street_lamps.cpp: In function 'int query(int, int, int)':
street_lamps.cpp:80:8: error: 'tr' was not declared in this scope
     if(tr[v].l>r||tr[v].r<l) return 0;
        ^~
street_lamps.cpp:80:8: note: suggested alternative: 'r'
     if(tr[v].l>r||tr[v].r<l) return 0;
        ^~
        r
street_lamps.cpp:81:11: error: 'tr' was not declared in this scope
     if(l<=tr[v].l&&tr[v].r<=r) return tr[v].sum;
           ^~
street_lamps.cpp:81:11: note: suggested alternative: 'r'
     if(l<=tr[v].l&&tr[v].r<=r) return tr[v].sum;
           ^~
           r
street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:88:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~
street_lamps.cpp:92:12: error: 'st' was not declared in this scope
         if(st[i].op==1) continue ;
            ^~
street_lamps.cpp:92:12: note: suggested alternative: 'qt'
         if(st[i].op==1) continue ;
            ^~
            qt
street_lamps.cpp:93:25: error: 'st' was not declared in this scope
         while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
                         ^~
street_lamps.cpp:93:25: note: suggested alternative: 'qt'
         while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
                         ^~
                         qt
street_lamps.cpp:93:40: error: 't' was not declared in this scope
         while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
                                        ^
street_lamps.cpp:93:58: error: 'q' was not declared in this scope
         while(tag<=mid&&st[tag].op==1&&t[st[tag].id].lp<=q[st[i].id].l) {
                                                          ^
street_lamps.cpp:97:9: error: 'ans' was not declared in this scope
         ans[st[i].id]+=query(1,1,q[st[i].id].tim);
         ^~~
street_lamps.cpp:97:13: error: 'st' was not declared in this scope
         ans[st[i].id]+=query(1,1,q[st[i].id].tim);
             ^~
street_lamps.cpp:97:13: note: suggested alternative: 'qt'
         ans[st[i].id]+=query(1,1,q[st[i].id].tim);
             ^~
             qt
street_lamps.cpp:97:34: error: 'q' was not declared in this scope
         ans[st[i].id]+=query(1,1,q[st[i].id].tim);
                                  ^
street_lamps.cpp:99:37: error: 't' was not declared in this scope
     for(int i=l;i<tag;i++) Modify(1,t[st[i].id].l,t[st[i].id].r,-1);
                                     ^
street_lamps.cpp:99:39: error: 'st' was not declared in this scope
     for(int i=l;i<tag;i++) Modify(1,t[st[i].id].l,t[st[i].id].r,-1);
                                       ^~
street_lamps.cpp:99:39: note: suggested alternative: 'qt'
     for(int i=l;i<tag;i++) Modify(1,t[st[i].id].l,t[st[i].id].r,-1);
                                       ^~
                                       qt
street_lamps.cpp:100:19: error: 'st' was not declared in this scope
     inplace_merge(st+l,st+mid+1,st+r+1,cmpl);
                   ^~
street_lamps.cpp:100:19: note: suggested alternative: 'qt'
     inplace_merge(st+l,st+mid+1,st+r+1,cmpl);
                   ^~
                   qt
street_lamps.cpp:100:5: error: 'inplace_merge' was not declared in this scope
     inplace_merge(st+l,st+mid+1,st+r+1,cmpl);
     ^~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:105:16: error: 's' was not declared in this scope
     scanf("%s",s+1);
                ^
street_lamps.cpp:105:5: error: 'scanf' was not declared in this scope
     scanf("%s",s+1);
     ^~~~~
street_lamps.cpp:113:9: error: 'R' was not declared in this scope
         R[i]=j;
         ^
street_lamps.cpp:114:9: error: 'pos' was not declared in this scope
         pos.insert(i);
         ^~~
street_lamps.cpp:115:9: error: 't' was not declared in this scope
         t[id[i]=++tot]=interval(i,j,1,m);
         ^
street_lamps.cpp:115:11: error: 'id' was not declared in this scope
         t[id[i]=++tot]=interval(i,j,1,m);
           ^~
street_lamps.cpp:115:11: note: suggested alternative: 'i'
         t[id[i]=++tot]=interval(i,j,1,m);
           ^~
           i
street_lamps.cpp:127:17: error: 'it' was not declared in this scope
                 it=pos.upper_bound(x);it--;
                 ^~
street_lamps.cpp:127:17: note: suggested alternative: 'i'
                 it=pos.upper_bound(x);it--;
                 ^~
                 i
street_lamps.cpp:127:20: error: 'pos' was not declared in this scope
                 it=pos.upper_bound(x);it--;
                    ^~~
street_lamps.cpp:129:17: error: 't' was not declared in this scope
                 t[id[LL]].r=i;
                 ^
street_lamps.cpp:129:19: error: 'id' was not declared in this scope
                 t[id[LL]].r=i;
                   ^~
street_lamps.cpp:129:19: note: suggested alternative: 'i'
                 t[id[LL]].r=i;
                   ^~
                   i
street_lamps.cpp:132:21: error: 'R' was not declared in this scope
                     R[LL]=x-1;
                     ^
street_lamps.cpp:134:22: error: 'RR' was not declared in this scope
                 if(x<RR) {
                      ^~
street_lamps.cpp:136:21: error: 'R' was not declared in this scope
                     R[x+1]=RR;
                     ^
street_lamps.cpp:141:17: error: 'it' was not declared in this scope
                 it=pos.upper_bound(x);
                 ^~
street_lamps.cpp:141:17: note: suggested alternative: 'i'
                 it=pos.upper_bound(x);
                 ^~
                 i
street_lamps.cpp:141:20: error: 'pos' was not declared in this scope
                 it=pos.upper_bound(x);
                    ^~~
street_lamps.cpp:145:30: error: 'R' was not declared in this scope
                         nowr=R[y];
                              ^
street_lamps.cpp:146:25: error: 't' was not declared in this scope
                         t[id[y]].r=i;
                         ^
street_lamps.cpp:146:27: error: 'id' was not declared in this scope
                         t[id[y]].r=i;
                           ^~
street_lamps.cpp:146:27: note: suggested alternative: 'i'
                         t[id[y]].r=i;
                           ^~
                           i
street_lamps.cpp:153:24: error: 'R' was not declared in this scope
                     if(R[y]==x-1) {
                        ^
street_lamps.cpp:155:25: error: 't' was not declared in this scope
                         t[id[y]].r=i;
                         ^
street_lamps.cpp:155:27: error: 'id' was not declared in this scope
                         t[id[y]].r=i;
                           ^~
street_lamps.cpp:155:27: note: suggested alternative: 'i'
                         t[id[y]].r=i;
                           ^~
                           i
street_lamps.cpp:159:17: error: 't' was not declared in this scope
                 t[id[nowl]=++tot]=interval(nowl,nowr,i+1,m);
                 ^
street_lamps.cpp:159:19: error: 'id' was not declared in this scope
                 t[id[nowl]=++tot]=interval(nowl,nowr,i+1,m);
                   ^~
street_lamps.cpp:159:19: note: suggested alternative: 'i'
                 t[id[nowl]=++tot]=interval(nowl,nowr,i+1,m);
                   ^~
                   i
street_lamps.cpp:160:17: error: 'R' was not declared in this scope
                 R[nowl]=nowr;
                 ^
street_lamps.cpp:164:13: error: 'q' was not declared in this scope
             q[++qt].l=Get(),q[qt].r=Get()-1;
             ^
street_lamps.cpp:169:9: error: 'st' was not declared in this scope
         st[++top]=node(1,i,t[i].rp);
         ^~
street_lamps.cpp:169:9: note: suggested alternative: 'qt'
         st[++top]=node(1,i,t[i].rp);
         ^~
         qt
street_lamps.cpp:169:28: error: 't' was not declared in this scope
         st[++top]=node(1,i,t[i].rp);
                            ^
street_lamps.cpp:172:9: error: 'st' was not declared in this scope
         st[++top]=node(2,i,q[i].r);
         ^~
street_lamps.cpp:172:9: note: suggested alternative: 'qt'
         st[++top]=node(2,i,q[i].r);
         ^~
         qt
street_lamps.cpp:172:28: error: 'q' was not declared in this scope
         st[++top]=node(2,i,q[i].r);
                            ^
street_lamps.cpp:174:10: error: 'st' was not declared in this scope
     sort(st+1,st+1+top,cmpr);
          ^~
street_lamps.cpp:174:10: note: suggested alternative: 'qt'
     sort(st+1,st+1+top,cmpr);
          ^~
          qt
street_lamps.cpp:174:5: error: 'sort' was not declared in this scope
     sort(st+1,st+1+top,cmpr);
     ^~~~
street_lamps.cpp:174:5: note: suggested alternative: 'short'
     sort(st+1,st+1+top,cmpr);
     ^~~~
     short
street_lamps.cpp:176:28: error: 'cout' was not declared in this scope
     for(int i=1;i<=qt;i++) cout<<ans[i]<<"\n";
                            ^~~~
street_lamps.cpp:176:28: note: suggested alternative: 'tot'
     for(int i=1;i<=qt;i++) cout<<ans[i]<<"\n";
                            ^~~~
                            tot
street_lamps.cpp:176:34: error: 'ans' was not declared in this scope
     for(int i=1;i<=qt;i++) cout<<ans[i]<<"\n";
                                  ^~~