oj.uz

Submission #1029078

# Submission time Handle Problem Language Result Execution time Memory
1029078 2024-07-20T12:05:28 Z atom Osumnjičeni (COCI21_osumnjiceni) C++17
30 / 110
 379 ms 35548 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

struct LazySegmentTree {
    vector <int> lzy, f;
    int n;
    LazySegmentTree(int _n) {
        n = _n;
        lzy.resize(n * 4 + 5, -1);
        f.resize(n * 4 + 5, 0);
    }

    int merge(int x, int y) { return max(x, y); }

    void push(int x, int l, int r) {
        if (lzy[x] == -1) return;
        int val = lzy[x];

        f[x << 1] = val;
        lzy[x << 1] = val;

        f[x << 1 | 1] = val;
        lzy[x << 1 | 1] = val;

        lzy[x] = -1;
        return;
    }

    void upd(int x, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            f[x] = val;
            lzy[x] = val;
            return;
        }
        int m = (l + r) / 2;
        push(x, l, r);
        upd(x << 1, l, m, u, v, val);
        upd(x << 1 | 1, m + 1, r, u, v, val);
        f[x] = merge(f[x << 1], f[x << 1 | 1]);
    }

    void upd(int l, int r, int val) { upd(1, 1, n, l, r, val); }

    int qry(int x, int l, int r, int u, int v) {
        if (l > v || r < u) return 0;
        if (u <= l && r <= v) return f[x];
        int m = (l + r) / 2;
        push(x, l, r);
        int ql = qry(x << 1, l, m, u, v);
        int qr = qry(x << 1 | 1, m + 1, r, u, v);
        return merge(ql, qr); 
    }

    int qry(int l, int r) { return qry(1, 1, n, l, r); }
};

const int LG = 18;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif

    vector <int> vals;
    int n, q;
    cin >> n;
    vector <pair <int, int>> segs(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> segs[i].first >> segs[i].second;
        vals.push_back(segs[i].first);
        vals.push_back(segs[i].second);
    }

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    for (int i = 1; i <= n; ++i) {
        segs[i].first = (int) (lower_bound(vals.begin(), vals.end(), segs[i].first) - vals.begin() + 1);
        segs[i].second = (int) (lower_bound(vals.begin(), vals.end(), segs[i].second) - vals.begin() + 1);
        debug(segs[i]);
    }

    LazySegmentTree st((int) vals.size());

    vector <int> nxt(n + 1, 0);
    int j = 1;
    for (int i = 1; i <= n; ++i) {
        while (j <= n && st.qry(segs[j].first, segs[j].second) == 0) {
            st.upd(segs[j].first, segs[j].second, 1);
            ++j;
        }
        nxt[i] = j;
        st.upd(segs[i].first, segs[i].second, 0);
    }
    nxt[n] = n + 1;

    vector <vector <int>> up(LG, vector <int> (n + 1, 0));
    // up(i, j) = nxt(..nxt(i)), use nxt() j times
    for (int i = 1; i <= n; ++i)
        up[0][i] = nxt[i];

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < LG; ++j)
            up[j][i] = up[j - 1][up[j - 1][i]];

    cin >> q;
    for (int _q = 1; _q <= q; ++_q) {
        int l, r;
        cin >> l >> r;
        
        int res = 1;
        while (nxt[l] <= r) {
            ++res;
            l = nxt[l];
        }
        cout << res << "\n";
    } 

    
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:9:20: warning: statement has no effect [-Wunused-value]
    9 | #define debug(...) 166
      |                    ^~~
Main.cpp:91:9: note: in expansion of macro 'debug'
   91 |         debug(segs[i]);
      |         ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 33896 KB Output is correct
2 Correct 334 ms 33536 KB Output is correct
3 Correct 301 ms 33484 KB Output is correct
4 Correct 351 ms 33992 KB Output is correct
5 Correct 334 ms 35272 KB Output is correct
6 Correct 42 ms 20936 KB Output is correct
7 Correct 47 ms 21288 KB Output is correct
8 Correct 54 ms 21452 KB Output is correct
9 Correct 56 ms 21964 KB Output is correct
10 Correct 74 ms 21196 KB Output is correct
11 Correct 205 ms 34240 KB Output is correct
12 Correct 192 ms 32204 KB Output is correct
13 Correct 198 ms 31944 KB Output is correct
14 Correct 218 ms 34244 KB Output is correct
15 Correct 223 ms 33368 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 45 ms 22352 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1372 KB Output is correct
2 Runtime error 7 ms 2140 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1372 KB Output is correct
2 Runtime error 7 ms 2140 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 379 ms 35548 KB Output is correct
2 Correct 360 ms 34876 KB Output is correct
3 Correct 366 ms 32328 KB Output is correct
4 Correct 347 ms 31948 KB Output is correct
5 Correct 361 ms 32944 KB Output is correct
6 Correct 54 ms 21168 KB Output is correct
7 Correct 54 ms 20804 KB Output is correct
8 Correct 54 ms 20936 KB Output is correct
9 Correct 71 ms 20792 KB Output is correct
10 Correct 70 ms 22472 KB Output is correct
11 Correct 183 ms 31692 KB Output is correct
12 Correct 240 ms 34832 KB Output is correct
13 Correct 193 ms 31952 KB Output is correct
14 Correct 209 ms 32712 KB Output is correct
15 Correct 223 ms 34616 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 82 ms 21444 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 33896 KB Output is correct
2 Correct 334 ms 33536 KB Output is correct
3 Correct 301 ms 33484 KB Output is correct
4 Correct 351 ms 33992 KB Output is correct
5 Correct 334 ms 35272 KB Output is correct
6 Correct 42 ms 20936 KB Output is correct
7 Correct 47 ms 21288 KB Output is correct
8 Correct 54 ms 21452 KB Output is correct
9 Correct 56 ms 21964 KB Output is correct
10 Correct 74 ms 21196 KB Output is correct
11 Correct 205 ms 34240 KB Output is correct
12 Correct 192 ms 32204 KB Output is correct
13 Correct 198 ms 31944 KB Output is correct
14 Correct 218 ms 34244 KB Output is correct
15 Correct 223 ms 33368 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 45 ms 22352 KB Output is correct
18 Correct 19 ms 1372 KB Output is correct
19 Runtime error 7 ms 2140 KB Execution killed with signal 11
20 Halted 0 ms 0 KB -