oj.uz

답안 #362302

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
362302 2021-02-02T15:25:54 Z arbor 가로등 (APIO19_street_lamps) C++17
20 / 100
 5000 ms 369200 KB 
#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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 323 ms 4596 KB Output is correct
2 Correct 471 ms 5100 KB Output is correct
3 Correct 973 ms 8772 KB Output is correct
4 Correct 4350 ms 203696 KB Output is correct
5 Correct 4519 ms 232360 KB Output is correct
6 Correct 4644 ms 206740 KB Output is correct
7 Correct 215 ms 22252 KB Output is correct
8 Execution timed out 5094 ms 366176 KB Time limit exceeded

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 876 KB Output is correct
2 Correct 4 ms 800 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 5 ms 1004 KB Output is correct
5 Correct 4758 ms 230312 KB Output is correct
6 Correct 4358 ms 230764 KB Output is correct
7 Correct 4043 ms 231564 KB Output is correct
8 Execution timed out 5054 ms 369200 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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 1978 ms 179016 KB Output is correct
6 Correct 3125 ms 196076 KB Output is correct
7 Correct 4392 ms 206212 KB Output is correct
8 Execution timed out 5060 ms 209932 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 376 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 323 ms 4596 KB Output is correct
9 Correct 471 ms 5100 KB Output is correct
10 Correct 973 ms 8772 KB Output is correct
11 Correct 4350 ms 203696 KB Output is correct
12 Correct 4519 ms 232360 KB Output is correct
13 Correct 4644 ms 206740 KB Output is correct
14 Correct 215 ms 22252 KB Output is correct
15 Execution timed out 5094 ms 366176 KB Time limit exceeded