oj.uz

Submission #385676

# Submission time Handle Problem Language Result Execution time Memory
385676 2021-04-04T17:31:39 Z valerikk Street Lamps (APIO19_street_lamps) C++17
100 / 100
 4295 ms 246332 KB 
#include <bits/stdc++.h>

using namespace std;

#define y1 y1111

#define mp make_pair
#define F first
#define S second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)a.size())
#define forn(i, n) for (int i = 0; i < (n); ++i)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1.1e9;
const ll INFL = 1.1e18;

const int N = 3e5 + 7;

struct Upd {
    int x, y, type;
};

int n, q;
string s, ss;
vector<Upd> upds[N];
pii qr[N];
set<int> st;
vector<int> yy[N];
vector<ll> f[N];
vector<int> cnt[N];

void innerUpd(int pp, int y, int t, int tp) {
    y = lower_bound(all(yy[pp]), y) - yy[pp].begin();
    for (int i = y + 1; i <= sz(yy[pp]); i += i & -i) {
        f[pp][i] += tp * t;
        cnt[pp][i] += tp;
    }
}

void upd(int x, int y, int t, int tp) {
    for (int i = x + 1; i < N; i += i & -i) innerUpd(i, y, t, tp);
}

ll innerGet(int pp, int y, int t) {
    y = lower_bound(all(yy[pp]), y) - yy[pp].begin();
    ll res = 0;
    for (int i = y; i > 0; i -= i & -i) res += cnt[pp][i] * t - f[pp][i];
    return res;
}

ll get(int x, int y, int t) {
    ll res = 0;
    for (int i = x; i > 0; i -= i & -i) res += innerGet(i, y, t);
    return res;
}

void addY(int x, int y) {
    for (int i = x + 1; i < N; i += i & -i) yy[i].pb(y);
}

void adds(int t, int x1, int y1, int x2, int y2, int type) {
    ++x2, ++y2;
    upds[t].pb({x1, y1, type});
    upds[t].pb({x1, y2, -type});
    upds[t].pb({x2, y1, -type});
    upds[t].pb({x2, y2, type});
}

void toggle(int i, int t) {
    int prv = *prev(st.lower_bound(i)), nxt = *st.upper_bound(i);
    int type = s[i] == '0' ? 1 : -1;
    adds(t, prv + 1, i + 1, i, nxt, type);
    if (s[i] == '0') {
        s[i] = '1';
        st.erase(i); 
    } else {
        s[i] = '0';
        st.insert(i);
    }
}

int main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q >> ss;
    s = string(n, '0');
    for (int i = -1; i <= n; ++i) st.insert(i);
    forn(i, n) {
        if (ss[i] == '1') {
            toggle(i, 0);
        }
    }
    for (int t = 0; t <= q; ++t) qr[t] = {-1, -1};
    for (int t = 1; t <= q; ++t) {
        string type;
        cin >> type;
        if (type == "toggle") {
            int i;
            cin >> i;
            --i;
            toggle(i, t);
        } else {
            int a, b;
            cin >> a >> b;
            --a, --b;
            qr[t] = {a, b};
        }
    }
    
    for (int t = 0; t <= q; ++t) {
        for (auto u : upds[t]) {
            addY(u.x, u.y);
        }
    }
    
    for (int i = 0; i < N; ++i) {
        sort(all(yy[i]));
        yy[i].erase(unique(all(yy[i])), yy[i].end());
        f[i] = vector<ll>(sz(yy[i]) + 1, 0ll);
        cnt[i] = vector<int>(sz(yy[i]) + 1, 0);
    }
    
    for (int t = 0; t <= q; ++t) {
        for (auto u : upds[t]) upd(u.x, u.y, t, u.type);
        if (qr[t].F != -1) cout << get(qr[t].F + 1, qr[t].S + 1, t) << "\n";
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47468 KB Output is correct
2 Correct 54 ms 47340 KB Output is correct
3 Correct 51 ms 47340 KB Output is correct
4 Correct 51 ms 47340 KB Output is correct
5 Correct 52 ms 47340 KB Output is correct
6 Correct 56 ms 47340 KB Output is correct
7 Correct 51 ms 47596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 98768 KB Output is correct
2 Correct 1081 ms 100276 KB Output is correct
3 Correct 1398 ms 98964 KB Output is correct
4 Correct 3287 ms 175288 KB Output is correct
5 Correct 3018 ms 172656 KB Output is correct
6 Correct 3332 ms 190120 KB Output is correct
7 Correct 268 ms 71040 KB Output is correct
8 Correct 3066 ms 246204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 47876 KB Output is correct
2 Correct 65 ms 47852 KB Output is correct
3 Correct 69 ms 47852 KB Output is correct
4 Correct 63 ms 48128 KB Output is correct
5 Correct 3607 ms 167504 KB Output is correct
6 Correct 3275 ms 167260 KB Output is correct
7 Correct 2847 ms 169504 KB Output is correct
8 Correct 3061 ms 240340 KB Output is correct
9 Correct 152 ms 50156 KB Output is correct
10 Correct 150 ms 50412 KB Output is correct
11 Correct 149 ms 50540 KB Output is correct
12 Correct 259 ms 65024 KB Output is correct
13 Correct 3071 ms 240444 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 47724 KB Output is correct
2 Correct 63 ms 47872 KB Output is correct
3 Correct 78 ms 47980 KB Output is correct
4 Correct 67 ms 47980 KB Output is correct
5 Correct 1490 ms 132584 KB Output is correct
6 Correct 2321 ms 154072 KB Output is correct
7 Correct 3216 ms 189740 KB Output is correct
8 Correct 4295 ms 212104 KB Output is correct
9 Correct 1480 ms 124660 KB Output is correct
10 Correct 1705 ms 147276 KB Output is correct
11 Correct 1483 ms 124840 KB Output is correct
12 Correct 1740 ms 147280 KB Output is correct
13 Correct 1472 ms 124664 KB Output is correct
14 Correct 1722 ms 147280 KB Output is correct
15 Correct 261 ms 70912 KB Output is correct
16 Correct 3099 ms 246332 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 47468 KB Output is correct
2 Correct 54 ms 47340 KB Output is correct
3 Correct 51 ms 47340 KB Output is correct
4 Correct 51 ms 47340 KB Output is correct
5 Correct 52 ms 47340 KB Output is correct
6 Correct 56 ms 47340 KB Output is correct
7 Correct 51 ms 47596 KB Output is correct
8 Correct 1002 ms 98768 KB Output is correct
9 Correct 1081 ms 100276 KB Output is correct
10 Correct 1398 ms 98964 KB Output is correct
11 Correct 3287 ms 175288 KB Output is correct
12 Correct 3018 ms 172656 KB Output is correct
13 Correct 3332 ms 190120 KB Output is correct
14 Correct 268 ms 71040 KB Output is correct
15 Correct 3066 ms 246204 KB Output is correct
16 Correct 65 ms 47876 KB Output is correct
17 Correct 65 ms 47852 KB Output is correct
18 Correct 69 ms 47852 KB Output is correct
19 Correct 63 ms 48128 KB Output is correct
20 Correct 3607 ms 167504 KB Output is correct
21 Correct 3275 ms 167260 KB Output is correct
22 Correct 2847 ms 169504 KB Output is correct
23 Correct 3061 ms 240340 KB Output is correct
24 Correct 152 ms 50156 KB Output is correct
25 Correct 150 ms 50412 KB Output is correct
26 Correct 149 ms 50540 KB Output is correct
27 Correct 259 ms 65024 KB Output is correct
28 Correct 3071 ms 240444 KB Output is correct
29 Correct 61 ms 47724 KB Output is correct
30 Correct 63 ms 47872 KB Output is correct
31 Correct 78 ms 47980 KB Output is correct
32 Correct 67 ms 47980 KB Output is correct
33 Correct 1490 ms 132584 KB Output is correct
34 Correct 2321 ms 154072 KB Output is correct
35 Correct 3216 ms 189740 KB Output is correct
36 Correct 4295 ms 212104 KB Output is correct
37 Correct 1480 ms 124660 KB Output is correct
38 Correct 1705 ms 147276 KB Output is correct
39 Correct 1483 ms 124840 KB Output is correct
40 Correct 1740 ms 147280 KB Output is correct
41 Correct 1472 ms 124664 KB Output is correct
42 Correct 1722 ms 147280 KB Output is correct
43 Correct 261 ms 70912 KB Output is correct
44 Correct 3099 ms 246332 KB Output is correct
45 Correct 539 ms 85692 KB Output is correct
46 Correct 654 ms 82748 KB Output is correct
47 Correct 1652 ms 108632 KB Output is correct
48 Correct 3021 ms 174488 KB Output is correct
49 Correct 160 ms 53868 KB Output is correct
50 Correct 156 ms 53828 KB Output is correct
51 Correct 172 ms 53996 KB Output is correct
52 Correct 221 ms 54528 KB Output is correct
53 Correct 162 ms 54380 KB Output is correct
54 Correct 168 ms 54636 KB Output is correct