oj.uz

Submission #364204

# Submission time Handle Problem Language Result Execution time Memory
364204 2021-02-08T11:44:46 Z grace0068 Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2936 ms 213852 KB 
// Dmitry _kun_ Sayutin (2019)

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::cerr;

using std::vector;
using std::map;
using std::array;
using std::set;
using std::string;

using std::pair;
using std::make_pair;

using std::tuple;
using std::make_tuple;
using std::get;

using std::min;
using std::abs;
using std::max;
using std::swap;

using std::unique;
using std::sort;
using std::generate;
using std::reverse;
using std::min_element;
using std::max_element;

#ifdef LOCAL
#define LASSERT(X) assert(X)
#else
#define LASSERT(X) {}
#endif

template <typename T>
T input() {
    T res;
    cin >> res;
    LASSERT(cin);
    return res;
}

template <typename IT>
void input_seq(IT b, IT e) {
    std::generate(b, e, input<typename std::remove_reference<decltype(*b)>::type>);
}

#define SZ(vec)         int((vec).size())
#define ALL(data)       data.begin(),data.end()
#define RALL(data)      data.rbegin(),data.rend()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()

vector<pair<int, int>> points;

struct segtree_node {
    vector<int> y_points;

    vector<int> tree;

    int query(int v, int l, int r, int y) {
        int res = tree[v];

        if (l == r - 1)
            return res;
        
        int m = l + (r - l) / 2;
        
        if (y >= y_points[m])
            res += query(2 * v + 2, m, r, y);
        else
            res += query(2 * v + 1, l, m, y);

        return res;
    }

    void seg_modif(int v, int l, int r, int maxy, int val) {
        if (y_points[r - 1] <= maxy) {
            tree[v] += val;
            return;
        }

        if (y_points[l] > maxy)
            return;

        int m = l + (r - l) / 2;
        seg_modif(2 * v + 1, l, m, maxy, val);
        seg_modif(2 * v + 2, m, r, maxy, val);
    }
};

vector<segtree_node> tree;

vector<int> seg_build(int v, int l, int r) {
    if (l == r - 1) {
        tree[v].y_points = {points[l].second};
    } else {
        int m = l + (r - l) / 2;

        auto r1 = seg_build(2 * v + 1, l, m);
        auto r2 = seg_build(2 * v + 2, m, r);

        tree[v].y_points.resize(SZ(r1) + SZ(r2));
        tree[v].y_points.resize(std::set_union(ALL(r1), ALL(r2), tree[v].y_points.begin())
                                - tree[v].y_points.begin());
    }

    tree[v].tree.resize(4 * SZ(tree[v].y_points));
    return tree[v].y_points;
}

int seg_query(int v, int l, int r, int x, int y) {
    int res = tree[v].query(0, 0, SZ(tree[v].y_points), y);

    if (l == r - 1)
        return res;

    int m = l + (r - l) / 2;
    if (make_pair(x, y) >= points[m])
        res += seg_query(2 * v + 2, m, r, x, y);
    else
        res += seg_query(2 * v + 1, l, m, x, y);

    return res;
}

void seg_modif(int v, int l, int r, int minx, int maxy, int val) {
    if (points[r - 1].first < minx)
        return;
    
    if (minx <= points[l].first) {
        tree[v].seg_modif(0, 0, SZ(tree[v].y_points), maxy, val);
        return;
    }

    int m = l + (r - l) / 2;
    seg_modif(2 * v + 1, l, m, minx, maxy, val);
    seg_modif(2 * v + 2, m, r, minx, maxy, val);
}

int main() {
    std::iostream::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // code here
    int n = input<int>();
    int q = input<int>();

    vector<char> state(n);
    for (int i = 0; i != n; ++i)
        state[i] = int(input<char>() == '1');

    vector<tuple<int, int, int>> in(q);
    for (int i = 0; i != q; ++i) {
        if (input<string>() == "toggle")
            in[i] = make_tuple(0, input<int>() - 1, -228);
        else {
            int a = input<int>() - 1;
            int b = input<int>() - 1;
            in[i] = make_tuple(1, a, b);
            points.emplace_back(a, b);
        }
    }

    sort(ALL(points));
    points.resize(std::unique(ALL(points)) - points.begin());
    
    tree.resize(4 * SZ(points));
    seg_build(0, 0, SZ(points));

    
    set<pair<int, int>> segments;
        
    for (int i = 0; i <= n;) {
        int j = i;
        while (j != n and state[j])
            ++j;
            
        segments.emplace(i, j);
        i = j + 1;
        
        //plane_op(i, j, 0);
    }        

    auto plane_op = [&](int a, int b, int val) {
        seg_modif(0, 0, SZ(points), a, b, val);
    };
        
    auto toggle = [&](int i, int tm) {
        // between i and i+1.
        
        if (state[i] == 0) {
            auto it = segments.lower_bound(make_pair(i + 1, -1));
            auto prev = std::prev(it);
            
            int A = prev->first;
            int B = it->second;
            
            segments.erase(it);
            segments.erase(prev);
            segments.emplace(A, B);
            
            plane_op(A, i, +tm);
            plane_op(i + 1, B, +tm);
            plane_op(A, B, -tm);
        } else {
            auto it = segments.upper_bound(make_pair(i, TYPEMAX(int)));
            --it;
            
            int A = it->first;
            int B = it->second;
                
            segments.erase(it);
            segments.emplace(A, i);
            segments.emplace(i + 1, B);

            plane_op(A, B, +tm);
            plane_op(A, i, -tm);
            plane_op(i + 1, B, -tm);
        }

        state[i] ^= 1;
    };
    
    for (int curtime = 1; curtime <= q; ++curtime) {
        if (get<0>(in[curtime - 1]) == 0)
            toggle(get<1>(in[curtime - 1]), curtime);
        else {
            int a = get<1>(in[curtime - 1]);
            int b = get<2>(in[curtime - 1]);
            
            int ans = seg_query(0, 0, SZ(points), a, b);
            auto it = std::prev(segments.upper_bound(make_pair(a, TYPEMAX(int))));
            
            if (it->first <= a and b <= it->second)
                ans += curtime;
            
            cout << ans << "\n";
        }
    }

    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 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 9316 KB Output is correct
2 Correct 262 ms 9700 KB Output is correct
3 Correct 440 ms 13012 KB Output is correct
4 Correct 1576 ms 91236 KB Output is correct
5 Correct 1675 ms 101696 KB Output is correct
6 Correct 1303 ms 78436 KB Output is correct
7 Correct 2388 ms 146688 KB Output is correct
8 Correct 1932 ms 136264 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 876 KB Output is correct
5 Correct 595 ms 24300 KB Output is correct
6 Correct 1277 ms 74032 KB Output is correct
7 Correct 1829 ms 127924 KB Output is correct
8 Correct 2449 ms 203680 KB Output is correct
9 Correct 219 ms 10980 KB Output is correct
10 Correct 231 ms 11228 KB Output is correct
11 Correct 255 ms 13404 KB Output is correct
12 Correct 2881 ms 213852 KB Output is correct
13 Correct 2438 ms 203612 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 2 ms 748 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2757 ms 204900 KB Output is correct
6 Correct 2048 ms 148436 KB Output is correct
7 Correct 1397 ms 90932 KB Output is correct
8 Correct 568 ms 17260 KB Output is correct
9 Correct 630 ms 45252 KB Output is correct
10 Correct 314 ms 9068 KB Output is correct
11 Correct 624 ms 45288 KB Output is correct
12 Correct 314 ms 9044 KB Output is correct
13 Correct 649 ms 45380 KB Output is correct
14 Correct 317 ms 8940 KB Output is correct
15 Correct 2936 ms 213720 KB Output is correct
16 Correct 2476 ms 203420 KB Output is correct

Subtask #5
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 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 218 ms 9316 KB Output is correct
9 Correct 262 ms 9700 KB Output is correct
10 Correct 440 ms 13012 KB Output is correct
11 Correct 1576 ms 91236 KB Output is correct
12 Correct 1675 ms 101696 KB Output is correct
13 Correct 1303 ms 78436 KB Output is correct
14 Correct 2388 ms 146688 KB Output is correct
15 Correct 1932 ms 136264 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 2 ms 492 KB Output is correct
18 Correct 2 ms 620 KB Output is correct
19 Correct 2 ms 876 KB Output is correct
20 Correct 595 ms 24300 KB Output is correct
21 Correct 1277 ms 74032 KB Output is correct
22 Correct 1829 ms 127924 KB Output is correct
23 Correct 2449 ms 203680 KB Output is correct
24 Correct 219 ms 10980 KB Output is correct
25 Correct 231 ms 11228 KB Output is correct
26 Correct 255 ms 13404 KB Output is correct
27 Correct 2881 ms 213852 KB Output is correct
28 Correct 2438 ms 203612 KB Output is correct
29 Correct 2 ms 876 KB Output is correct
30 Correct 2 ms 748 KB Output is correct
31 Correct 2 ms 620 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 2757 ms 204900 KB Output is correct
34 Correct 2048 ms 148436 KB Output is correct
35 Correct 1397 ms 90932 KB Output is correct
36 Correct 568 ms 17260 KB Output is correct
37 Correct 630 ms 45252 KB Output is correct
38 Correct 314 ms 9068 KB Output is correct
39 Correct 624 ms 45288 KB Output is correct
40 Correct 314 ms 9044 KB Output is correct
41 Correct 649 ms 45380 KB Output is correct
42 Correct 317 ms 8940 KB Output is correct
43 Correct 2936 ms 213720 KB Output is correct
44 Correct 2476 ms 203420 KB Output is correct
45 Correct 119 ms 5992 KB Output is correct
46 Correct 247 ms 8168 KB Output is correct
47 Correct 1022 ms 68704 KB Output is correct
48 Correct 1758 ms 109540 KB Output is correct
49 Correct 276 ms 12528 KB Output is correct
50 Correct 259 ms 12000 KB Output is correct
51 Correct 297 ms 14176 KB Output is correct
52 Correct 487 ms 69728 KB Output is correct
53 Correct 487 ms 69768 KB Output is correct
54 Correct 487 ms 69728 KB Output is correct