oj.uz

Submission #362305

# Submission time Handle Problem Language Result Execution time Memory
362305 2021-02-02T15:29:41 Z arbor Street Lamps (APIO19_street_lamps) C++17
40 / 100
 5000 ms 363520 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];
struct pii {
    int first, second;
};
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 316 ms 1516 KB Output is correct
2 Correct 454 ms 1772 KB Output is correct
3 Correct 962 ms 4844 KB Output is correct
4 Correct 4259 ms 198900 KB Output is correct
5 Correct 4383 ms 226960 KB Output is correct
6 Correct 4506 ms 202044 KB Output is correct
7 Correct 195 ms 16364 KB Output is correct
8 Execution timed out 5100 ms 363056 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 876 KB Output is correct
4 Correct 5 ms 1004 KB Output is correct
5 Correct 4643 ms 226036 KB Output is correct
6 Correct 4326 ms 226072 KB Output is correct
7 Correct 3873 ms 226492 KB Output is correct
8 Correct 4807 ms 363232 KB Output is correct
9 Correct 98 ms 1516 KB Output is correct
10 Correct 106 ms 1516 KB Output is correct
11 Correct 113 ms 1772 KB Output is correct
12 Correct 190 ms 16492 KB Output is correct
13 Correct 4804 ms 363520 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 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 748 KB Output is correct
5 Correct 1877 ms 173292 KB Output is correct
6 Correct 3006 ms 190560 KB Output is correct
7 Correct 4165 ms 201100 KB Output is correct
8 Execution timed out 5108 ms 206980 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 316 ms 1516 KB Output is correct
9 Correct 454 ms 1772 KB Output is correct
10 Correct 962 ms 4844 KB Output is correct
11 Correct 4259 ms 198900 KB Output is correct
12 Correct 4383 ms 226960 KB Output is correct
13 Correct 4506 ms 202044 KB Output is correct
14 Correct 195 ms 16364 KB Output is correct
15 Execution timed out 5100 ms 363056 KB Time limit exceeded