Submission #154971

#	Time	Username	Problem	Language	Result	Execution time	Memory
154971		Akashi	Street Lamps (APIO19_street_lamps)	C++14	100 / 100	2698 ms	287868 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

int n, q;
char t[25], light[300005];

struct interv{
    int x, y, tmp;

    bool operator < (const interv &aux)const{
        if(x != aux.x) return x < aux.x;
        return y < aux.y;
    }
};
set <interv> s;

struct node{
    int val;
    node *left, *right;

    node(){
        val = 0;
        left = right = NULL;
    }
};

struct data_structure{
    node *bit[300005];

    void update_seg(node *nod, int x, int val, int st = 1, int dr = n){
        nod->val += val;
        if(st == dr) return ;

        int mij = (st + dr) / 2;
        if(x <= mij){
            if(nod->left == NULL) nod->left = new node;
            update_seg(nod->left, x, val, st, mij);
        }
        else{
            if(nod->right == NULL) nod->right = new node;
            update_seg(nod->right, x, val, mij + 1, dr);
        }
    }

    void update(int x, int y, int val){
        for(int i = x; i <= n ; i = i + (i & (-i)))
            update_seg(bit[i], y, val);
    }

    int query_seg(node *nod, int x, int y, int st = 1, int dr = n){
        if(x <= st && dr <= y) return nod->val;

        int mij = (st + dr) / 2;
        int a1 = 0, a2 = 0;
        if(x <= mij){
            if(nod->left != NULL) a1 = query_seg(nod->left, x, y, st, mij);
        }
        if(mij + 1 <= y){
            if(nod->right != NULL) a2 = query_seg(nod->right, x, y, mij + 1, dr);
        }

        return a1 + a2;
    }

    int query(int x, int y){
        int Sum = 0;
        for(int i = x; i > 0 ; i = i - (i & (-i)))
            Sum = Sum + query_seg(bit[i], y, n);
        return Sum;
    }

    void build(){
        for(int i = 1; i <= n ; ++i)
            bit[i] = new node;
    }
};
data_structure A;

void elim(int x, int tmp){
    set <interv> :: iterator it = s.lower_bound({x + 1, 0, 0});
    --it;

    A.update(it->x, it->y, tmp - it->tmp);

    if(x - 1 >= it->x) s.insert({it->x, x - 1, tmp});
    if(x + 1 <= it->y) s.insert({x + 1, it->y, tmp});

    s.erase(it);
}

void add(int x, int tmp){
    if(s.empty()){
        s.insert({x, x, tmp});
        return ;
    }

    set <interv> :: iterator it = s.lower_bound({x + 1, 0, 0});

    if(it != s.begin() && it != s.end()){
        set <interv> :: iterator it2 = it;
        --it2;

        if(it2->y == x - 1 && it->x == x + 1){
            A.update(it->x, it->y, tmp - it->tmp);
            A.update(it2->x, it2->y, tmp - it2->tmp);

            s.insert({it2->x, it->y, tmp});

            s.erase(it);
            s.erase(it2);
            return ;
        }
    }

    set <interv> :: iterator it2 = it;
    if(it2 != s.begin()) --it2;
    if(it == s.end()) --it;

    if(it2->y == x - 1){
        A.update(it2->x, it2->y, tmp - it2->tmp);

        s.insert({it2->x, x, tmp});
        s.erase(it2);
        return ;
    }

    if(it->x == x + 1){
        A.update(it->x, it->y, tmp - it->tmp);

        s.insert({x, it->y, tmp});
        s.erase(it);
        return ;
    }

    s.insert({x, x, tmp});
}

int main(){

    scanf("%d%d", &n, &q);
    scanf("%s", light + 1);

    for(int i = 1; i <= n ; ++i){
        if(light[i] == '0') continue ;
        int j = i;
        while(light[j + 1] == '1' && j + 1 <= n) ++j;

        s.insert({i, j, 0});
        i = j;
    }

    A.build();
    int x, y;
    for(int tmp = 1; tmp <= q ; ++tmp){
        scanf("%s", t);

        if(t[0] == 'q'){
            scanf("%d%d", &x, &y);
            --y;
            int v = A.query(x, y);

            set <interv> :: iterator it = s.lower_bound({x + 1, 0, 0});

            if(it != s.begin()){
                --it;
                if(it->x <= x && y <= it->y) v = v + (tmp - it->tmp);
            }

            printf("%d\n", v);
        }
        else{
            scanf("%d", &x);
            if(x == 3){
                bool ok = 0;

            }

            if(light[x] == '1') light[x] = '0', elim(x, tmp);
            else light[x] = '1', add(x, tmp);
        }
    }


    return 0;
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:174:22: warning: unused variable 'ok' [-Wunused-variable]
                 bool ok = 0;
                      ^~
street_lamps.cpp:140: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:141:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", light + 1);
     ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", t);
         ~~~~~^~~~~~~~~
street_lamps.cpp:158:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:172:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~

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