oj.uz

Submission #516898

# Submission time Handle Problem Language Result Execution time Memory
516898 2022-01-22T08:10:32 Z blue Street Lamps (APIO19_street_lamps) C++17
100 / 100
 1630 ms 419592 KB 
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;

const int mx = 300'000;

int n, q;
int s[1+mx];

set<int> offpoints;




int Z = (1<<19);

struct stamp_tree
{
    vi stamp = vi(Z<<1, 0);

    void set(int l, int r, int t)
    {
        l += Z;
        r += Z+1;
        while(l < r)
        {
            if(l & 1) stamp[l++] = t;
            if(r & 1) stamp[--r] = t;
            l >>= 1;
            r >>= 1;
        }
    }

    int query(int i)
    {
        int ans = 0;
        for(i += Z; i >= 1; i >>= 1) ans = max(ans, stamp[i]);
        return ans;
    }
};

stamp_tree stt;










// vvi total_time = vvi(1+mx, vi(1+mx, 0));

struct col_tree
{
    int l;
    int r;

    int lp = 0;

    col_tree* left = NULL;
    col_tree* right = NULL;

    col_tree()
    {
        ;
    }

    col_tree(int L, int R)
    {
        l = L;
        r = R;
    }

    void add(int L, int R, int V)
    {
        // cerr << "col add\n";
        if(R < l || r < L) return;
        else if(L <= l && r <= R)
        {
            lp += V;
        }
        else
        {
            if(L <= (l+r)/2)
            {
                if(left == NULL) left = new col_tree(l, (l+r)/2);
                left->add(L, R, V);
            }

            if(R >= (l+r)/2+1)
            {
                if(right == NULL) right = new col_tree((l+r)/2+1, r);
                right->add(L, R, V);
            }
        }
    }

    int query(int I)
    {
        // cerr << "col query\n";
        if(l == r) return lp;
        else if(I <= (l+r)/2)
        {
            if(left == NULL) return lp;
            else return lp + left->query(I);
        }
        else
        {
            if(right == NULL) return lp;
            else return lp + right->query(I);
        }
    }
};







struct row_tree
{
    int l;
    int r;

    col_tree lp;

    row_tree* left = NULL;
    row_tree* right = NULL;

    row_tree()
    {
        ;
    }

    row_tree(int L, int R)
    {
        l = L;
        r = R;
        lp = col_tree(1, n);
    }

    void add(int L, int R, int X, int Y, int V)
    {
        if(R < l || r < L) return;
        else if(L <= l && r <= R) lp.add(X, Y, V);
        else
        {
            if(left == NULL) left = new row_tree(l, (l+r)/2); //OPTIMIZE THIS!!!
            left->add(L, R, X, Y, V);

            if(right == NULL) right = new row_tree((l+r)/2+1, r);
            right->add(L, R, X, Y, V);
        }
    }

    int query(int I, int J)
    {
        if(l == r) return lp.query(J);
        else if(I <= (l+r)/2)
        {
            if(left == NULL) return lp.query(J);
            else return left->query(I, J) + lp.query(J);
        }
        else
        {
            if(right == NULL) return lp.query(J);
            else return right->query(I, J) + lp.query(J);
        }
    }
};






// col_tree ST[1+mx];
row_tree ST;






int get_value(int l, int r)
{
 // return ST[l].query(r);
    return ST.query(l, r);
}

void range_add(int l, int r, int x, int y, int v)
{
    // for(int i = l; i <= r; i++)
    //     ST[i].add(x, y, v);
    ST.add(l, r, x, y, v);
}














void add_triangle(int l, int r, int t)
{
    stt.set(l, r, t);
}

void remove_triangle(int l, int r, int t)
{
    int tt = stt.query(l);
    range_add(l, r, l, r, t - tt);
}

void switch_on(int i, int t)
{
    offpoints.erase(i);

    auto it = offpoints.lower_bound(i);
    int r = *it;
    it--;
    int l = *it;

    remove_triangle(l+1, i-1, t);
    remove_triangle(i+1, r-1, t);
    add_triangle(l+1, r-1, t);
}

void switch_off(int i, int t)
{
    auto it = offpoints.lower_bound(i);
    int r = *it;
    it--;
    int l = *it;

    offpoints.insert(i);

    remove_triangle(l+1, r-1, t);
    add_triangle(l+1, i-1, t);
    add_triangle(i+1, r-1, t);
}

int query(int l, int r, int t)
{
    int y = *offpoints.lower_bound(l);
    if(y > r) return get_value(l, r) + t - stt.query(l);
    else return get_value(l, r);
}
























int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;

    string t;
    cin >> t;

    for(int i = 0; i < n; i++)
        s[i+1] = (t[i] == '1');

    for(int i = 1; i <= n; i++)
        if(s[i] == 0)
            offpoints.insert(i);

    offpoints.insert(0);
    offpoints.insert(n+1);

    // for(int i = 1; i <= n; i++) ST[i] = col_tree(1, n);
    ST = row_tree(1, n);


    for(int j = 1; j <= q; j++)
    {
        string qr;
        cin >> qr;
        if(qr == "toggle")
        {
            int i;
            cin >> i;

            if(s[i] == 0)
            {
                s[i] = 1;
                switch_on(i, j);
            }
            else
            {
                s[i] = 0;
                switch_off(i, j);
            }
        }
        else
        {
            int a, b;
            cin >> a >> b;

            cout << query(a, b-1, j) << '\n';
        }
    }
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 5604 KB Output is correct
2 Correct 227 ms 9512 KB Output is correct
3 Correct 392 ms 19424 KB Output is correct
4 Correct 906 ms 202396 KB Output is correct
5 Correct 1196 ms 354764 KB Output is correct
6 Correct 1004 ms 224132 KB Output is correct
7 Correct 424 ms 26448 KB Output is correct
8 Correct 157 ms 13908 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5328 KB Output is correct
2 Correct 3 ms 5196 KB Output is correct
3 Correct 4 ms 5216 KB Output is correct
4 Correct 3 ms 4460 KB Output is correct
5 Correct 1630 ms 419592 KB Output is correct
6 Correct 1538 ms 406208 KB Output is correct
7 Correct 1446 ms 353412 KB Output is correct
8 Correct 144 ms 13892 KB Output is correct
9 Correct 115 ms 8136 KB Output is correct
10 Correct 93 ms 8428 KB Output is correct
11 Correct 95 ms 8608 KB Output is correct
12 Correct 332 ms 26440 KB Output is correct
13 Correct 114 ms 13872 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4428 KB Output is correct
2 Correct 3 ms 4684 KB Output is correct
3 Correct 4 ms 4844 KB Output is correct
4 Correct 5 ms 4940 KB Output is correct
5 Correct 328 ms 26800 KB Output is correct
6 Correct 760 ms 149856 KB Output is correct
7 Correct 937 ms 223436 KB Output is correct
8 Correct 1319 ms 292300 KB Output is correct
9 Correct 237 ms 8796 KB Output is correct
10 Correct 198 ms 7524 KB Output is correct
11 Correct 211 ms 8840 KB Output is correct
12 Correct 183 ms 7680 KB Output is correct
13 Correct 260 ms 8804 KB Output is correct
14 Correct 203 ms 7520 KB Output is correct
15 Correct 373 ms 26464 KB Output is correct
16 Correct 126 ms 14020 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4428 KB Output is correct
2 Correct 2 ms 4428 KB Output is correct
3 Correct 2 ms 4428 KB Output is correct
4 Correct 2 ms 4372 KB Output is correct
5 Correct 2 ms 4428 KB Output is correct
6 Correct 2 ms 4428 KB Output is correct
7 Correct 2 ms 4428 KB Output is correct
8 Correct 167 ms 5604 KB Output is correct
9 Correct 227 ms 9512 KB Output is correct
10 Correct 392 ms 19424 KB Output is correct
11 Correct 906 ms 202396 KB Output is correct
12 Correct 1196 ms 354764 KB Output is correct
13 Correct 1004 ms 224132 KB Output is correct
14 Correct 424 ms 26448 KB Output is correct
15 Correct 157 ms 13908 KB Output is correct
16 Correct 4 ms 5328 KB Output is correct
17 Correct 3 ms 5196 KB Output is correct
18 Correct 4 ms 5216 KB Output is correct
19 Correct 3 ms 4460 KB Output is correct
20 Correct 1630 ms 419592 KB Output is correct
21 Correct 1538 ms 406208 KB Output is correct
22 Correct 1446 ms 353412 KB Output is correct
23 Correct 144 ms 13892 KB Output is correct
24 Correct 115 ms 8136 KB Output is correct
25 Correct 93 ms 8428 KB Output is correct
26 Correct 95 ms 8608 KB Output is correct
27 Correct 332 ms 26440 KB Output is correct
28 Correct 114 ms 13872 KB Output is correct
29 Correct 3 ms 4428 KB Output is correct
30 Correct 3 ms 4684 KB Output is correct
31 Correct 4 ms 4844 KB Output is correct
32 Correct 5 ms 4940 KB Output is correct
33 Correct 328 ms 26800 KB Output is correct
34 Correct 760 ms 149856 KB Output is correct
35 Correct 937 ms 223436 KB Output is correct
36 Correct 1319 ms 292300 KB Output is correct
37 Correct 237 ms 8796 KB Output is correct
38 Correct 198 ms 7524 KB Output is correct
39 Correct 211 ms 8840 KB Output is correct
40 Correct 183 ms 7680 KB Output is correct
41 Correct 260 ms 8804 KB Output is correct
42 Correct 203 ms 7520 KB Output is correct
43 Correct 373 ms 26464 KB Output is correct
44 Correct 126 ms 14020 KB Output is correct
45 Correct 95 ms 6744 KB Output is correct
46 Correct 111 ms 6992 KB Output is correct
47 Correct 474 ms 97788 KB Output is correct
48 Correct 958 ms 202048 KB Output is correct
49 Correct 91 ms 8464 KB Output is correct
50 Correct 97 ms 8468 KB Output is correct
51 Correct 117 ms 8644 KB Output is correct
52 Correct 87 ms 8928 KB Output is correct
53 Correct 97 ms 8960 KB Output is correct
54 Correct 89 ms 8924 KB Output is correct