제출 #230593

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230593		lyc	가로등 (APIO19_street_lamps)	C++14	20 / 100	1431 ms	56476 KiB

street_lamps

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

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int MX_N = 3e5+5;
const int MX_Q = 3e5+5;
int N, Q;
string S;
vector<array<int,2>> change;
vector<array<int,3>> query;
vector<array<int,4>> itv;
set<array<int,2>> cur;
int ans[MX_Q];

struct FenwickTree {
    vector<ll> ft; int n;
    void init(int _n) { n = _n; ft.assign(n+1,0); }
    void update(int i, int x) { for (; i <= n; i += i&-i) ft[i] += x; }
    ll query(int i) { ll s = 0; for (; i; i -= i&-i) s += ft[i]; return s; }
    ll query(int i, int j) { return query(j)-query(i-1); }
} ft, ft2;

void cdq(int l, int r, vector<array<int,4>>& a, vector<array<int,3>>& b) {
    if (l > r) return;
    if (l == r) {
        for (auto& x : a) {
            ft.update(x[1], (x[3]?1:-1)*x[0]);
            ft2.update(x[1], (x[3]?-1:1));
        }
        for (auto& y : b) {
            ans[y[0]] += ft.query(y[1]);
            ans[y[0]] += ft2.query(y[1]) * y[0];
        }
        for (auto& x : a) {
            ft.update(x[1], -(x[3]?1:-1)*x[0]);
            ft2.update(x[1], -(x[3]?-1:1));
        }
        return;
    }

    int m = (l+r) >> 1;
    vector<array<int,4>> a1, a2;
    for (auto& x : a) (x[0] <= m ? a1 : a2).push_back(x);
    vector<array<int,3>> b1, b2;
    for (auto& y : b) (y[0] <= m ? b1 : b2).push_back(y);
    cdq(l,m,a1,b1);
    cdq(m+1,r,a2,b2);

    sort(ALL(a1), [](array<int,4> p, array<int,4> q){
            return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0]))));
            });
    sort(ALL(b2), [](array<int,3> p, array<int,3> q){
            return (p[2]>q[2]||(p[2]==q[2]&&(p[1]>q[1]||(p[1]==q[1]&&p[0]>q[0]))));
            });

    //TRACE(l _ r);
    //for (auto& x : a) TRACE(x[0] _ x[1] _ x[2] _ x[3]);
    //for (auto& y : b) TRACE(y[0] _ y[1] _ y[2]);
    //cout << endl;

    int i, j;
    for (i = 0, j = 0; i < SZ(a1) || j < SZ(b2); ) {
        if (i < SZ(a1) && (j >= SZ(b2) || a1[i][2] >= b2[j][2])) {
            ft.update(a1[i][1], (a1[i][3]?1:-1)*a1[i][0]);
            ft2.update(a1[i][1], (a1[i][3]?-1:1));
            ++i;
        } else {
            ans[b2[j][0]] += ft.query(b2[j][1]);
            ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0];
            ++j;
        }
    }
    for (;j < SZ(b2);) {
        ans[b2[j][0]] += ft.query(b2[j][1]);
        ans[b2[j][0]] += ft2.query(b2[j][1]) * b2[j][0];
        ++j;
    }
    FOR(k,0,i-1){
        ft.update(a1[k][1], -(a1[k][3]?1:-1)*a1[k][0]);
        ft2.update(a1[k][1], -(a1[k][3]?-1:1));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N >> Q >> S; S = '^' + S + '0';
    FOR(i,1,Q){
        string T; cin >> T;
        if (T == "toggle") {
            int I; cin >> I;
            change.push_back({i,I});
        } else {
            int A, B; cin >> A >> B;
            --B;
            query.push_back({i,A,B});
        }
    }

    int len = 0;
    FOR(i,1,N+1){
        if (S[i] == '0') {
            if (len) {
                cur.insert({i-len,i-1});
                itv.push_back({0,i-len,i-1,0});
            }
            len = 0;
        } else ++len;
    }

    for (auto& x : change) {
        //cout << x[1] << ' ' << x[1] << " vs ";
        //for (auto& y : cur) cout << y[0] << ' ' << y[1] << " | ";
        //cout << endl;

        if (S[x[1]] == '0') {
            auto it = cur.upper_bound({x[1],0});
            array<int,2> y = {x[1],x[1]};
            if (it != cur.end() && y[1]+1 == (*it)[0]) {
                auto z = *it; cur.erase(it);
                itv.push_back({x[0],z[0],z[1],1});
                y[1] = z[1];
                it = cur.upper_bound({x[1],0});
            }
            if (it != cur.begin() && (*(--it))[1]+1 == y[0]) {
                auto z = *it; cur.erase(it);
                itv.push_back({x[0],z[0],z[1],1});
                y[0] = z[0];
            }
            cur.insert(y);
            itv.push_back({x[0],y[0],y[1],0});
            S[x[1]] = '1';
        } else {
            auto it = cur.upper_bound({x[1],0});
            assert(it != cur.begin());
            auto y = *(--it); cur.erase(it);
            assert(y[1] >= x[1]);
            itv.push_back({x[0],y[0],y[1],1});
            if (y[0] < x[1]) {
                cur.insert({y[0],x[1]-1});
                itv.push_back({x[0],y[0],x[1]-1,0});
            }
            if (x[1] < y[1]) {
                cur.insert({x[1]+1,y[1]});
                itv.push_back({x[0],x[1]+1,y[1],0});
            }
            S[x[1]] = '0';
        }
    }

    for (auto& x : cur) {
        itv.push_back({Q,x[0],x[1],1});
    }

    //for (auto& x : itv) { TRACE(x[0] _ x[1] _ x[2] _ x[3]); }

    memset(ans,0,sizeof ans);
    ft.init(N);
    ft2.init(N);
    cdq(0,Q,itv,query);

    for (auto& q : query) {
        cout << ans[q[0]] << '\n';
    }
}

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