oj.uz

Submission #172178

# Submission time Handle Problem Language Result Execution time Memory
172178 2019-12-31T14:04:44 Z errorgorn Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 423888 KB 
#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

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.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 4904 KB Output is correct
2 Correct 605 ms 6008 KB Output is correct
3 Correct 1421 ms 22392 KB Output is correct
4 Correct 3824 ms 346412 KB Output is correct
5 Correct 3373 ms 265048 KB Output is correct
6 Correct 4268 ms 373548 KB Output is correct
7 Correct 161 ms 7264 KB Output is correct
8 Correct 171 ms 8528 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1272 KB Output is correct
2 Correct 6 ms 1144 KB Output is correct
3 Correct 5 ms 888 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Execution timed out 5043 ms 413404 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 5 ms 1144 KB Output is correct
4 Correct 6 ms 1400 KB Output is correct
5 Correct 1158 ms 184004 KB Output is correct
6 Correct 2541 ms 285944 KB Output is correct
7 Correct 4022 ms 373688 KB Output is correct
8 Execution timed out 5099 ms 423888 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 401 ms 4904 KB Output is correct
9 Correct 605 ms 6008 KB Output is correct
10 Correct 1421 ms 22392 KB Output is correct
11 Correct 3824 ms 346412 KB Output is correct
12 Correct 3373 ms 265048 KB Output is correct
13 Correct 4268 ms 373548 KB Output is correct
14 Correct 161 ms 7264 KB Output is correct
15 Correct 171 ms 8528 KB Output is correct
16 Correct 6 ms 1272 KB Output is correct
17 Correct 6 ms 1144 KB Output is correct
18 Correct 5 ms 888 KB Output is correct
19 Correct 3 ms 256 KB Output is correct
20 Execution timed out 5043 ms 413404 KB Time limit exceeded
21 Halted 0 ms 0 KB -