oj.uz

답안 #230593

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230593 2020-05-10T14:14:23 Z lyc 가로등 (APIO19_street_lamps) C++14
20 / 100
 1431 ms 56476 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 71 ms 7024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 1664 KB Output is correct
2 Correct 7 ms 1664 KB Output is correct
3 Correct 8 ms 1664 KB Output is correct
4 Correct 6 ms 1664 KB Output is correct
5 Correct 1328 ms 41916 KB Output is correct
6 Correct 1431 ms 56204 KB Output is correct
7 Correct 1200 ms 56476 KB Output is correct
8 Correct 501 ms 18472 KB Output is correct
9 Correct 309 ms 10208 KB Output is correct
10 Correct 337 ms 12508 KB Output is correct
11 Correct 330 ms 12380 KB Output is correct
12 Correct 488 ms 18600 KB Output is correct
13 Correct 494 ms 18480 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -