Submission #172178

#	Time	Username	Problem	Language	Result	Execution time	Memory
172178		errorgorn	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	5099 ms	423888 KiB

street_lamps

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

const int MAXN=300005;

long long __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;
    long long val=0; ///stores the length that section is on on "on and off" sections
    int on_now=0; ///stores if section is on now
    ///note that time something is on is E-S + E-S +...

    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,bool j){ ///j is true to toggle on
        if (j){
            on_now++;
            val-=__CLOCK;
        }
        else{
            on_now--;
            val+=__CLOCK;
        }

        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,l->on_now=temp->on_now;
                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,r->on_now=temp->on_now;
                if (temp->e<=r->m) r->l=temp;
                else r->r=temp;
            }
            r->update(i,j);
        }
    }

    long long query(int i,int j){
        if (i<=s && e<=j) return val+__CLOCK*on_now;
        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->on_now=on_now;
        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,bool 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);
        }
    }

    long long 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<ii> 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(curr);
                curr=ii(-1,-1);
            }
        }
    }

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

    for (auto &it:range){
        root->update(it.second,it.first,true);
    }

    ///when [A,B] is toggled, we add that into segment tree then when we query on 2d segment, we query [[1,A],[B,N]] for all segments that toally contain the segment we are querying
    ///note that when updating we say true when we turn on and false when we turn off

    char buf[10];
    set<ii>::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);
            printf("%lld\n",root->query(1,a,b-1,MAXN));
        }
        else{ ///toggle
            scanf("%d",&a);
            if (lamps[a]=='1'){
                it=range.lower_bound(ii(a,-1));
                temp=*it;
                if (temp.first!=a){
                    root->update(a+1,temp.first,true);
                    range.insert(ii(temp.first,a+1));
                }
                if (temp.second!=a){
                    root->update(temp.second,a-1,true);
                    range.insert(ii(a-1,temp.second));
                }
                root->update(temp.second,temp.first,false);
                range.erase(temp);
                lamps[a]='0';
            }
            else{
                temp=ii(a,a);
                if (lamps[a+1]=='1'){
                    it=range.lower_bound(ii(a+1,-1));
                    temp.first=(*it).first;
                    root->update((*it).second,(*it).first,false);
                    range.erase(it);
                }
                if (lamps[a-1]=='1'){
                    it=range.lower_bound(ii(a-1,-1));
                    temp.second=(*it).second;
                    root->update((*it).second,(*it).first,false);
                    range.erase(it);
                }
                root->update(temp.second,temp.first,true);
                range.insert(temp);
                lamps[a]='1';
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In function 'ii lca(int, int, int, int, int)':
street_lamps.cpp:13:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
street_lamps.cpp: In constructor 'node::node(int, int)':
street_lamps.cpp:29: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:98: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:180:24: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[10]' [-Wformat=]
         scanf("%s",&buf);
                    ~~~~^
street_lamps.cpp:147: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:151:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&ch);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:180:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s",&buf);
         ~~~~~^~~~~~~~~~~
street_lamps.cpp:182: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:186: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: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20