oj.uz

Submission #362303

# Submission time Handle Problem Language Result Execution time Memory
362303 2021-02-02T15:28:11 Z arbor Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 369188 KB 
#pragma GCC optimize "Ofast"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
#define eb emplace_back
#define pb push_back
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
const int MN = 3e5 + 5, MM = 2.2e7;
int N, Q, a[MN], rt[MN], ndc;
int ls[MM], rs[MM];
pii sum[MM];

pii merge(pii p, pii q) {
    return {p.first + q.first, p.second + q.second};
}

void upd(int &i, int l, int r, int x, int u, int v) {
    if (!i) i = ++ndc;
    if (l == r) {
        sum[i].first += u;
        sum[i].second += v;
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) upd(ls[i], l, m, x, u, v);
    else upd(rs[i], m + 1, r, x, u, v);
    sum[i] = merge(sum[ls[i]], sum[rs[i]]);
}

pii get(int &i, int l, int r, int ql, int qr) {
    if (!i || l > qr || r < ql) return {0, 0};
    if (l >= ql && r <= qr) return sum[i];
    int m = (l + r) / 2;
    return merge(get(ls[i], l, m, ql, qr), get(rs[i], m + 1, r, ql, qr));
}

void modify(int x, int y, int u, int v) {
    for (; x <= N + 1; x += x & -x) upd(rt[x], 1, N + 1, y, u, v);
}

pii qry(int x, int y) {
    pii ret = {0, 0};
    for (; x; x -= x & -x) ret = merge(ret, get(rt[x], 1, N + 1, 1, y));
    return ret;
}

set<int> dat;

void add(int x, int t) {
    // [pre + 1, x] * [x, nxt - 1]
    auto it = dat.find(x), pre = it, nxt = it;
    pre--, nxt++;
    modify(*pre + 1, x, 1, -t);
    modify(*pre + 1, *nxt, -1, t);
    modify(x + 1, x, -1, t);
    modify(x + 1, *nxt, 1, -t);
    // cout << "[" << *pre + 1 << ", " << x << "] * [" << x << ", " << *nxt - 1 << "]" << '\n';
    dat.erase(x);
}

void rmv(int x, int t) {
    auto nxt = dat.upper_bound(x), pre = nxt;
    pre--;
    modify(*pre + 1, x, -1, t);
    modify(*pre + 1, *nxt, 1, -t);
    modify(x + 1, x, 1, -t);
    modify(x + 1, *nxt, -1, t);
    dat.insert(x);
}

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N >> Q;
    dat.insert(0), dat.insert(N + 1);
    for (int i = 1; i <= N; i++) {
        char c; cin >> c;
        a[i] = c - '0';
        dat.insert(i);
    }
    for (int i = 1; i <= N; i++) {
        if (a[i]) {
            add(i, 0);
        }
    }
    for (int i = 1; i <= Q; i++) {
        string op; cin >> op;
        if (op == "query") {
            int l, r; cin >> l >> r; r--;
            auto [u, v] = qry(l, r);
            cout << i * u + v << '\n';
        } else {
            int x; cin >> x;
            if (a[x]) rmv(x, i), a[x] = 0;
            else add(x, i), a[x] = 1;
        }
    }
    return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 4716 KB Output is correct
2 Correct 439 ms 5132 KB Output is correct
3 Correct 884 ms 9068 KB Output is correct
4 Correct 4120 ms 202152 KB Output is correct
5 Correct 4286 ms 229792 KB Output is correct
6 Correct 4411 ms 204796 KB Output is correct
7 Correct 207 ms 18796 KB Output is correct
8 Execution timed out 5076 ms 364296 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 876 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 5 ms 1004 KB Output is correct
5 Correct 4599 ms 226056 KB Output is correct
6 Correct 4244 ms 226228 KB Output is correct
7 Correct 3793 ms 226604 KB Output is correct
8 Correct 4657 ms 363244 KB Output is correct
9 Correct 100 ms 4076 KB Output is correct
10 Correct 109 ms 4332 KB Output is correct
11 Correct 117 ms 4716 KB Output is correct
12 Correct 192 ms 22252 KB Output is correct
13 Correct 4635 ms 369188 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Correct 4 ms 748 KB Output is correct
4 Correct 5 ms 876 KB Output is correct
5 Correct 1837 ms 173420 KB Output is correct
6 Correct 2963 ms 190920 KB Output is correct
7 Correct 4105 ms 201572 KB Output is correct
8 Execution timed out 5087 ms 207884 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 313 ms 4716 KB Output is correct
9 Correct 439 ms 5132 KB Output is correct
10 Correct 884 ms 9068 KB Output is correct
11 Correct 4120 ms 202152 KB Output is correct
12 Correct 4286 ms 229792 KB Output is correct
13 Correct 4411 ms 204796 KB Output is correct
14 Correct 207 ms 18796 KB Output is correct
15 Execution timed out 5076 ms 364296 KB Time limit exceeded