제출 #603846

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
603846		OttoTheDino	가로등 (APIO19_street_lamps)	C++17	20 / 100	5073 ms	84764 KiB

street_lamps

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

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define pb                          push_back
#define fi                          first
#define se                          second
#define len(a)                      (int)a.size()
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;

const int mx = 3e5;
int ans[mx+1], ft[mx+1];
vector<vi> g;

void upd (int x, int id) {
    for (;id<=mx;id+=id&(-id)) ft[id] += x;
}
int qry (int id) {
    int res = 0;
    for (;id;id-=id&(-id)) res += ft[id];
    return res;
}

void cdq (int l, int r) {
    if (l==r) return;
    int mid = (l+r)/2;
    cdq (l, mid);
    cdq (mid+1, r);
    sort(g.begin()+l, g.begin()+r+1);
    vii undo;
    vector<vi> nxt;
    int a = l, b = mid+1, k = l;
    while (k<=r) {
        if (a>mid || (b<=r && g[b]<g[a])) nxt.pb(g[b++]);
        else nxt.pb(g[a++]);
        ++k;
    }
    rep (i,l,r) g[i] = nxt[i-l];
    rep (i,l,r) {
        int y = g[i][1], id = g[i][2], delt = g[i][3], t = g[i][4];
        if (t>mid) ans[id] += qry(y);
        else {
            upd(delt,y);
            undo.pb({delt,y});
        }
    }
    for (ii el : undo) upd(-el.fi, el.se);
}

int main() {
    int n, q; cin >> n >> q;
    bool b[n+1]; 
    string s; cin >> s;
    set<int> st;
    st.insert(0);
    st.insert(n+1);
    rep (i,1,n) {
        b[i] = s[i-1]-'0';
        if (!b[i]) st.insert(i);
    }
    vi get;
    rep (i,1,q) {
        string tp; cin >> tp;
        int t = len(g);
        if (tp[0]=='t') {
            int u; cin >> u;
            int prv = *--st.lower_bound(u)+1, nxt = *st.upper_bound(u)-1, c = 2*b[u]-1;
            g.pb({prv,mx-nxt,0,c*i,t++}); 
            if (u+1<=mx) g.pb({u+1,mx-nxt,0,-c*i,t++});
            if (u-1>0) g.pb({prv,mx-(u-1),0,-c*i,t++});
            if (b[u]) st.insert(u);
            else st.erase(u);
            b[u] ^= 1;
        }
        else {
            int x, y; cin >> x >> y;
            --y;
            get.pb(i);
            if (*st.lower_bound(x)>y) ans[i] += i;
            g.pb({x,mx-y,i,0,t++});
        }
    }
    cdq(0,len(g)-1);
    for (int el : get) cout << ans[el] << "\n";

    return 0;
}

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