Submission #258742

#	Time	Username	Problem	Language	Result	Execution time	Memory
258742		doowey	가로등 (APIO19_street_lamps)	C++14	100 / 100	3417 ms	286548 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)3e5 + 10;
const int M = (int)3e7;

struct Node{
    int f1;
    int f2;
    int li;
    int ri;
};

Node T[M];

int mx_id = 0;

int n;
struct ST1D{
    int root=-1;
    int add_node(){
        T[mx_id++]={0, 0ll, -1, -1};
        return mx_id - 1 ;
    }
    void init(){
        root=add_node();
    }
    void upd(int node, int cl, int cr, int pos, int ti, int vi){
        if(cl == cr){
            T[node].f1 += vi;
            T[node].f2 += -ti * 1ll * vi;
            return ;
        }
        int mid = (cl + cr) / 2;
        if(mid >= pos){
            if(T[node].li == -1){
                int nx = add_node();
                T[node].li = nx;
            }
            upd(T[node].li, cl, mid, pos, ti, vi);
        }
        else{
            if(T[node].ri == -1){
                int nx = add_node();
                T[node].ri = nx;
            }
            upd(T[node].ri, mid + 1, cr, pos, ti, vi);
        }
        T[node].f1 = T[node].f2 = 0;
        if(T[node].li != -1) {
            T[node].f1 += T[T[node].li].f1;
            T[node].f2 += T[T[node].li].f2;
        }
        if(T[node].ri != -1){
            T[node].f1 += T[T[node].ri].f1;
            T[node].f2 += T[T[node].ri].f2;
        }
    }
    ll query(int node, int cl, int cr, int tl, int tr, int tt){
        if(node == -1 || cr < tl || cl > tr) return 0;
        if(cl >= tl && cr <= tr){
            return tt * 1ll * T[node].f1 + T[node].f2;
        }
        int mid = (cl + cr) / 2;
        return query(T[node].li, cl, mid, tl, tr, tt) + query(T[node].ri, mid + 1, cr, tl, tr, tt);
    }
};

ST1D seg[N * 4 + 512];

void upd_it(int node, int cl, int cr, int pos, int ti, int vi, int ri){
    if(seg[node].root==-1)
        seg[node].init();
    seg[node].upd(seg[node].root, 1, n, ri, ti, vi);
    if(cl == cr)
        return;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        upd_it(node * 2, cl, mid, pos, ti, vi, ri);
    else
        upd_it(node * 2 + 1, mid + 1, cr, pos, ti, vi, ri);
}

ll ask(int node, int cl, int cr, int tl, int tr, int R, int tt){
    if(cr < tl)
        return 0;
    if(cl > tr)
        return 0;
    if(cl >= tl && cr <= tr){
        if(seg[node].root != -1)
            return seg[node].query(seg[node].root,1,n,R,n,tt);
        else
            return 0;
    }
    int mid = (cl + cr) / 2;
    return ask(node * 2, cl, mid, tl, tr, R, tt) + ask(node * 2 + 1, mid + 1, cr, tl, tr, R, tt);
}

set<pii> segs;
int vl[N];
int vv[N];

void toggle(int id, int ti){
    if(vl[id] == 0){
        auto it = segs.lower_bound(mp(id + 1, -1));
        int nl, nr;
        nl = nr = id;
        if(it != segs.end()){
            if(it->fi == id + 1){
                upd_it(1, 1, n, it->fi, ti, -1, it->se);
                nr = it->se;
                it = segs.erase(it);
            }
        }
        if(it != segs.begin()){
            it--;
            if(it->se == id - 1){
                upd_it(1, 1, n, it->fi, ti, -1, it->se);
                nl = it->fi;
                segs.erase(it);
            }
        }
        segs.insert(mp(nl, nr));
        upd_it(1, 1, n, nl, ti, +1, nr);
        vl[id] ^= 1;
    }
    else{
        auto it = segs.lower_bound(mp(id + 1, -1));
        it--;
        int cl = it->fi;
        int cr = it->se;
        segs.erase(it);
        upd_it(1, 1, n, cl, ti, -1, cr);
        if(cl < id){
            segs.insert(mp(cl, id - 1));
            upd_it(1, 1, n, cl, ti, +1, id-1);
        }
        if(id < cr){
            segs.insert(mp(id + 1, cr));
            upd_it(1, 1, n, id + 1, ti, +1, cr);
        }
        vl[id] ^= 1;
    }
}


int main(){
    fastIO;
    int q;
    cin >> n >> q;
    char f;
    int lv = 0;
    for(int i = 1; i <= n; i ++ ){
        cin >> f;
        vl[i]=f-'0';
        if(vl[i] == 1){
            if(lv == 0) lv = i;
        }
        if(lv > 0){
            if(vl[i] == 0){
                segs.insert(mp(lv, i-1));
                upd_it(1, 1, n, lv, 0, +1, i-1);
                lv = 0;
            }
            else if(i == n){
                segs.insert(mp(lv, n));
                upd_it(1, 1, n, lv, 0, +1, n);
                lv = 0;
            }
        }
    }

    string typ;
    int li, ri;
    for(int tv = 1; tv <= q; tv ++ ){
        cin >> typ;
        if(typ == "toggle"){
            cin >> li;
            toggle(li,tv);
        }
        else{
            cin >> li >> ri;
            ri--;
            cout << ask(1, 1, n, 1, li, ri, tv) << "\n";
        }
    }
    return 0;
}

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