oj.uz

Submission #120526

# Submission time Handle Problem Language Result Execution time Memory
120526 2019-06-24T17:31:09 Z model_code Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2815 ms 208896 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 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 199 ms 6324 KB Output is correct
2 Correct 244 ms 6208 KB Output is correct
3 Correct 459 ms 8812 KB Output is correct
4 Correct 1504 ms 85996 KB Output is correct
5 Correct 1520 ms 96364 KB Output is correct
6 Correct 1235 ms 73260 KB Output is correct
7 Correct 2213 ms 146916 KB Output is correct
8 Correct 1741 ms 130080 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 4 ms 768 KB Output is correct
5 Correct 593 ms 19736 KB Output is correct
6 Correct 1184 ms 69232 KB Output is correct
7 Correct 1714 ms 122604 KB Output is correct
8 Correct 2204 ms 197860 KB Output is correct
9 Correct 209 ms 8172 KB Output is correct
10 Correct 224 ms 8164 KB Output is correct
11 Correct 253 ms 10212 KB Output is correct
12 Correct 2691 ms 208232 KB Output is correct
13 Correct 2198 ms 197832 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 896 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2791 ms 200084 KB Output is correct
6 Correct 2161 ms 143856 KB Output is correct
7 Correct 1329 ms 86640 KB Output is correct
8 Correct 617 ms 13688 KB Output is correct
9 Correct 591 ms 42784 KB Output is correct
10 Correct 282 ms 7016 KB Output is correct
11 Correct 581 ms 42864 KB Output is correct
12 Correct 291 ms 7012 KB Output is correct
13 Correct 572 ms 42796 KB Output is correct
14 Correct 283 ms 8952 KB Output is correct
15 Correct 2815 ms 208896 KB Output is correct
16 Correct 2257 ms 198764 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 199 ms 6324 KB Output is correct
9 Correct 244 ms 6208 KB Output is correct
10 Correct 459 ms 8812 KB Output is correct
11 Correct 1504 ms 85996 KB Output is correct
12 Correct 1520 ms 96364 KB Output is correct
13 Correct 1235 ms 73260 KB Output is correct
14 Correct 2213 ms 146916 KB Output is correct
15 Correct 1741 ms 130080 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 3 ms 512 KB Output is correct
18 Correct 3 ms 640 KB Output is correct
19 Correct 4 ms 768 KB Output is correct
20 Correct 593 ms 19736 KB Output is correct
21 Correct 1184 ms 69232 KB Output is correct
22 Correct 1714 ms 122604 KB Output is correct
23 Correct 2204 ms 197860 KB Output is correct
24 Correct 209 ms 8172 KB Output is correct
25 Correct 224 ms 8164 KB Output is correct
26 Correct 253 ms 10212 KB Output is correct
27 Correct 2691 ms 208232 KB Output is correct
28 Correct 2198 ms 197832 KB Output is correct
29 Correct 4 ms 896 KB Output is correct
30 Correct 4 ms 768 KB Output is correct
31 Correct 3 ms 512 KB Output is correct
32 Correct 3 ms 384 KB Output is correct
33 Correct 2791 ms 200084 KB Output is correct
34 Correct 2161 ms 143856 KB Output is correct
35 Correct 1329 ms 86640 KB Output is correct
36 Correct 617 ms 13688 KB Output is correct
37 Correct 591 ms 42784 KB Output is correct
38 Correct 282 ms 7016 KB Output is correct
39 Correct 581 ms 42864 KB Output is correct
40 Correct 291 ms 7012 KB Output is correct
41 Correct 572 ms 42796 KB Output is correct
42 Correct 283 ms 8952 KB Output is correct
43 Correct 2815 ms 208896 KB Output is correct
44 Correct 2257 ms 198764 KB Output is correct
45 Correct 103 ms 5012 KB Output is correct
46 Correct 233 ms 6772 KB Output is correct
47 Correct 866 ms 66280 KB Output is correct
48 Correct 1623 ms 105392 KB Output is correct
49 Correct 260 ms 9956 KB Output is correct
50 Correct 254 ms 9700 KB Output is correct
51 Correct 286 ms 11364 KB Output is correct
52 Correct 508 ms 66916 KB Output is correct
53 Correct 512 ms 66808 KB Output is correct
54 Correct 498 ms 66876 KB Output is correct