Submission #172193

#	Time	Username	Problem	Language	Result	Execution time	Memory
172193		errorgorn	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	3306 ms	317048 KiB

street_lamps

#include <cstdio>
#include <set>
#include <utility>
using namespace std;
typedef pair<int,int> ii;
typedef pair<ii,int> iii;

const int MAXN=300005;

int __CLOCK=0; ///global time
///also __CLOCK is cool variable name :sunglasses:

ii lca(int s,int e,int l,int r,int pos){ ///find lca of 2 nodes
    int m=s+e>>1;
    if (r<=m && m<pos) return ii(s,e);
    else if (pos<=m && m<l) return ii(s,e);
    if (pos<=m) return lca(s,m,l,r,pos);
    else return lca(m+1,e,l,r,pos);
}

struct node{
    int s,e,m;
    int val=0; ///stores the length that section is on on "on and off" sections

    node *l=nullptr,*r=nullptr;

    node(int _s,int _e){
        s=_s,e=_e,m=s+e>>1;
    }

    inline bool inside(int i){
        return s<=i && i<=e;
    }

    void update(int i,int j){
        val+=j;

        if (s==e) return;
        if (i<=m){
            if (l==nullptr) l=new node(i,i);
            else if (!l->inside(i)){
                node *temp=l;
                ii child=lca(s,e,l->s,l->e,i);
                l=new node(child.first,child.second);
                l->val=temp->val;
                if (temp->e<=l->m) l->l=temp;
                else l->r=temp;
            }
            l->update(i,j);
        }
        else{
            if (r==nullptr) r=new node(i,i);
            else if (!r->inside(i)){
                node *temp=r;
                ii child=lca(s,e,r->s,r->e,i);
                r=new node(child.first,child.second);
                r->val=temp->val;
                if (temp->e<=r->m) r->l=temp;
                else r->r=temp;
            }
            r->update(i,j);
        }
    }

    int query(int i,int j){
        if (i<=s && e<=j) return val;
        else if (j<=m) return (l==nullptr)?0:l->query(i,j);
        else if (m<i) return (r==nullptr)?0:r->query(i,j);
        else return ((l==nullptr)?0:l->query(i,j))+((r==nullptr)?0:r->query(i,j));
    }

    node* clone(){ ///cloning seg tree for 2d seg tree
        node* res=new node(s,e);
        res->val=val;
        res->l=(l==nullptr)?nullptr:l->clone();
        res->r=(r==nullptr)?nullptr:r->clone();
        return res;
    }

};

struct node2d{
    int s,e,m;
    node *val;

    node2d *l=nullptr,*r=nullptr;

    node2d(int _s,int _e, node *_val){
        s=_s,e=_e,m=s+e>>1;
        val=_val;
    }

    inline bool inside(int i){
        return s<=i && i<=e;
    }

    void update(int i,int j,int k){
        val->update(j,k);
        if (s==e) return;
        if (i<=m){
            if (l==nullptr) l=new node2d(i,i,new node(0,MAXN));
            else if (!l->inside(i)){
                node2d *temp=l;
                ii child=lca(s,e,l->s,l->e,i);
                l=new node2d(child.first,child.second,temp->val->clone());
                if (temp->e<=l->m) l->l=temp;
                else l->r=temp;
            }
            l->update(i,j,k);
        }
        else{
            if (r==nullptr) r=new node2d(i,i,new node(0,MAXN));
            else if (!r->inside(i)){
                node2d *temp=r;
                ii child=lca(s,e,r->s,r->e,i);
                r=new node2d(child.first,child.second,temp->val->clone());
                if (temp->e<=r->m) r->l=temp;
                else r->r=temp;
            }
            r->update(i,j,k);
        }
    }

    int query(int i,int j,int i2,int j2){
        if (i<=s && e<=j) return val->query(i2,j2);
        else if (j<=m) return (l==nullptr)?0:l->query(i,j,i2,j2);
        else if (m<i) return (r==nullptr)?0:r->query(i,j,i2,j2);
        else return ((l==nullptr)?0:l->query(i,j,i2,j2))+((r==nullptr)?0:r->query(i,j,i2,j2));
    }
}*root=new node2d(0,MAXN,new node(0,MAXN));

int n,q;
char lamps[MAXN];
set<iii> range;

int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&q);
    char ch;
    ii curr=ii(-1,-1); ///sentinal
    for (int x=1;x<=n;x++){
        scanf(" %c",&ch);
        lamps[x]=ch;
        if (ch=='1'){
            if (curr.first==-1) curr.second=x;
            curr.first=x;
        }
        else{
            if (curr!=ii(-1,-1)){
                range.insert(iii(curr,__CLOCK));
                curr=ii(-1,-1);
            }
        }
    }

    if (curr!=ii(-1,-1)) range.insert(iii(curr,__CLOCK));

    char buf[10];
    set<iii>::iterator it;
    ii temp;
    int a,b;
    while (q--){
        __CLOCK++; ///update global current time
        scanf("%s",&buf);
        if (buf[0]=='q'){ ///query
            scanf("%d%d",&a,&b);
            it=range.lower_bound(iii(ii(b-1,-1),-1));
            if (it==range.end() || (*it).first.second>a) printf("%d\n",root->query(1,a,b-1,MAXN));
            else printf("%d\n",root->query(1,a,b-1,MAXN)+__CLOCK-(*it).second);
            
        }
        else{ ///toggle
            scanf("%d",&a);
            if (lamps[a]=='1'){
                it=range.lower_bound(iii(ii(a,-1),-1));
                temp=(*it).first;
                if (temp.first!=a){
                    range.insert(iii(ii(temp.first,a+1),__CLOCK));
                }
                if (temp.second!=a){
                    range.insert(iii(ii(a-1,temp.second),__CLOCK));
                }
                root->update(temp.second,temp.first,__CLOCK-(*it).second);
                range.erase(it);
                lamps[a]='0';
            }
            else{
                temp=ii(a,a);
                if (lamps[a+1]=='1'){
                    it=range.lower_bound(iii(ii(a+1,-1),-1));
                    temp.first=(*it).first.first;
                    root->update((*it).first.second,(*it).first.first,__CLOCK-(*it).second);
                    range.erase(it);
                }
                if (lamps[a-1]=='1'){
                    it=range.lower_bound(iii(ii(a-1,-1),-1));
                    temp.second=(*it).first.second;
                    root->update((*it).first.second,(*it).first.first,__CLOCK-(*it).second);
                    range.erase(it);
                }
                range.insert(iii(temp,__CLOCK));
                lamps[a]='1';
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'ii lca(int, int, int, int, int)':
street_lamps.cpp:14:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
street_lamps.cpp: In constructor 'node::node(int, int)':
street_lamps.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
street_lamps.cpp: In constructor 'node2d::node2d(int, int, node*)':
street_lamps.cpp:89:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         s=_s,e=_e,m=s+e>>1;
                     ~^~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:164:24: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
         scanf("%s",&buf);
                    ~~~~^
street_lamps.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:142:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&ch);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:164:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&buf);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d",&a,&b);
             ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:173:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a);
             ~~~~~^~~~~~~~~

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