제출 #268302

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
268302		evpipis	가로등 (APIO19_street_lamps)	C++11	100 / 100	3796 ms	408720 KiB

street_lamps

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

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 3e5+5;
set<ii> mys;
int light[len]; // n_len

struct seg_tree{
    struct node{
        int sum, num;
        node *lef, *rig;

        node(int s = 0, int n = 0, node *l = NULL, node *r = NULL){
            sum = s;
            num = n;
            lef = l;
            rig = r;
        }
    };

    typedef node *pnode;
    pnode null, root;
    int mx;

    seg_tree(int m = 0){
        mx = m;
        null = new node();
        null->lef = null->rig = null;
        root = null;
    }

    pnode update(pnode t, int l, int r, int i, int s, int n){
        if (t == null)
            t = new node(0, 0, null, null);
        t->sum += s;
        t->num += n;

        if (l == r)
            return t;

        int mid = (l+r)/2;
        if (i <= mid)
            t->lef = update(t->lef, l, mid, i, s, n);
        else
            t->rig = update(t->rig, mid+1, r, i, s, n);
        return t;
    }

    void upd(int y, int sum, int num){
        root = update(root, 1, mx, y, sum, num);
    }

    ii query(pnode t, int l, int r, int i, int j){
        if (r < i || j < l)
            return mp(0, 0);
        if (i <= l && r <= j)
            return mp(t->sum, t->num);

        int mid = (l+r)/2;
        ii lef = query(t->lef, l, mid, i, j);
        ii rig = query(t->rig, mid+1, r, i, j);
        return mp(lef.fi+rig.fi, lef.se+rig.se);
    }

    ii ask(int y){
        return query(root, 1, mx, y, mx);
    }
};

struct bit{
    seg_tree tree[len];
    int mx;

    bit(int r = 0, int c = 0){
        mx = r;

        for (int i = 1; i <= r; i++)
            tree[i] = seg_tree(c);
    }

    void upd(int x, int y, int sum, int num){
        while (x <= mx)
            tree[x].upd(y, sum, num), x += x&(-x);
    }

    int ask(int x, int y, int tim){
        int sum = 0, num = 0;
        while (x > 0){
            sum += tree[x].ask(y).fi;
            num += tree[x].ask(y).se;
            x -= x&(-x);
        }

        return sum + num*tim;
    }
};

bit data;

ii rig(int i){
    auto it = mys.lower_bound(mp(i, 0));
    if (it == mys.end())
        return mp(-1, -1);
    return *it;
}

ii lef(int i){
    auto it = mys.lower_bound(mp(i+1, 0));
    if (it == mys.begin())
        return mp(-1, -1);
    return *(--it);
}

void print(){
    printf("current intervals:");
    for (auto it: mys)
        printf(" (%d, %d)", it.fi, it.se);
    printf("\n");
}

void toggle(int i, int t = 0){
    light[i] ^= 1;

    if (light[i] == 1){
        ii cur = mp(i, i), l = lef(i-1), r = rig(i+1);
        if (l.se+1 == cur.fi){
            // remove l and update data and extend cur
            mys.erase(l);
            data.upd(l.fi, l.se, +t, -1);
            cur.fi = l.fi;
        }
        if (cur.se == r.fi-1){
            // remove r and update data and extend cur
            mys.erase(r);
            data.upd(r.fi, r.se, +t, -1);
            cur.se = r.se;
        }
        // insert cur and update data
        mys.insert(cur);
        data.upd(cur.fi, cur.se, -t, +1);
    }
    else{
        ii cur = lef(i), l = mp(cur.fi, i-1), r = mp(i+1, cur.se);
        // remove cur and update data
        mys.erase(cur);
        data.upd(cur.fi, cur.se, +t, -1);
        if (l.fi <= l.se){
            // insert l and update data
            mys.insert(l);
            data.upd(l.fi, l.se, -t, +1);
        }
        if (r.fi <= r.se){
            // insert r and update data
            mys.insert(r);
            data.upd(r.fi, r.se, -t, +1);
        }
    }

    //print();
}

int main(){
    int n, q;
    scanf("%d %d ", &n, &q);

    data = bit(n, n);

    for (int i = 1; i <= n; i++){
        char temp;
        scanf("%c", &temp);
        if (temp == '1')
            toggle(i);
    }

    for (int i = 1; i <= q; i++){
        char str[15];
        scanf("%s", str);
        if (str[0] == 'q'){
            int a, b;
            scanf("%d %d", &a, &b);
            b--;

            printf("%d\n", data.ask(a, b, i));
            //printf("asked for interval (%d, %d)\n", a, b);
        }
        else{
            int pos;
            scanf("%d", &pos);
            toggle(pos, i);
        }

        //printf("%d) ", i);
        //print();
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  170 |     scanf("%d %d ", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  176 |         scanf("%c", &temp);
      |         ~~~~~^~~~~~~~~~~~~
street_lamps.cpp:183:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  183 |         scanf("%s", str);
      |         ~~~~~^~~~~~~~~~~
street_lamps.cpp:186:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  186 |             scanf("%d %d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:194:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  194 |             scanf("%d", &pos);
      |             ~~~~~^~~~~~~~~~~~

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