oj.uz

Submission #362311

# Submission time Handle Problem Language Result Execution time Memory
362311 2021-02-02T15:42:43 Z arbor Street Lamps (APIO19_street_lamps) C++14
40 / 100
 5000 ms 364136 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
#define gc getchar_unlocked()
#define pc(x) putchar_unlocked(x)
template<typename T> void scan(T &x){x = 0;register bool _=0;register T c=gc;_=c==45;c=_?gc:c;while(c<48||c>57)c=gc;for(;c<48||c>57;c=gc);for(;c>47&&c<58;c=gc)x=(x<<3)+(x<<1)+(c&15);x=_?-x:x;}
template<typename T> void printn(T n){register bool _=0;_=n<0;n=_?-n:n;char snum[65];int i=0;do{snum[i++]=n%10+48;n/= 10;}while(n);--i;if (_)pc(45);while(i>=0)pc(snum[i--]);}
template<typename First, typename ... Ints> void scan(First &arg, Ints&... rest){scan(arg);scan(rest...);}
template<typename T> void print(T n){printn(n);pc(10);}
template<typename First, typename ... Ints> void print(First arg, Ints... rest){printn(arg);pc(32);print(rest...);}
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;

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

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

int main() {
    //ios_base::sync_with_stdio(0), cin.tie(0);
    scan(N, Q);
    dat.insert(0), dat.insert(N + 1);
    for (int i = 1; i <= N; i++) {
        a[i] = gc - '0';
        dat.insert(i);
    }
    gc;
    for (int i = 1; i <= N; i++) {
        if (a[i]) {
            add(i, 0);
        }
    }
    for (int i = 1; i <= Q; i++) {
        if (gc == 'q') {
            int l, r; scan(l, r); r--;
            pii p = qry(l, r);
            print(i * p.first + p.second);
        } else {
            int x; scan(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 0 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 272 ms 1388 KB Output is correct
2 Correct 356 ms 1644 KB Output is correct
3 Correct 851 ms 4768 KB Output is correct
4 Correct 4234 ms 198596 KB Output is correct
5 Correct 4377 ms 226776 KB Output is correct
6 Correct 4748 ms 201648 KB Output is correct
7 Correct 103 ms 16252 KB Output is correct
8 Execution timed out 5131 ms 364136 KB Time limit exceeded

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 876 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Correct 3 ms 876 KB Output is correct
4 Correct 4 ms 1004 KB Output is correct
5 Correct 4504 ms 226468 KB Output is correct
6 Correct 4155 ms 226596 KB Output is correct
7 Correct 3717 ms 227072 KB Output is correct
8 Correct 4655 ms 363732 KB Output is correct
9 Correct 33 ms 1772 KB Output is correct
10 Correct 46 ms 1900 KB Output is correct
11 Correct 36 ms 2028 KB Output is correct
12 Correct 102 ms 16876 KB Output is correct
13 Correct 4774 ms 363460 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 6 ms 780 KB Output is correct
5 Correct 1815 ms 173528 KB Output is correct
6 Correct 3168 ms 191124 KB Output is correct
7 Correct 4402 ms 201704 KB Output is correct
8 Execution timed out 5078 ms 206852 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 0 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 272 ms 1388 KB Output is correct
9 Correct 356 ms 1644 KB Output is correct
10 Correct 851 ms 4768 KB Output is correct
11 Correct 4234 ms 198596 KB Output is correct
12 Correct 4377 ms 226776 KB Output is correct
13 Correct 4748 ms 201648 KB Output is correct
14 Correct 103 ms 16252 KB Output is correct
15 Execution timed out 5131 ms 364136 KB Time limit exceeded