oj.uz

Submission #1028991

# Submission time Handle Problem Language Result Execution time Memory
1028991 2024-07-20T10:59:47 Z atom Osumnjičeni (COCI21_osumnjiceni) C++17
10 / 110
 1000 ms 19912 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, 0);
        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]) return;
        int val = lzy[x];

        f[x << 1] = max(f[x << 1], val);
        lzy[x << 1] = val;

        f[x << 1 | 1] = max(f[x << 1 | 1], val);
        lzy[x << 1 | 1] = val;

        lzy[x] = 0;
        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] = max(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); }
};

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());
    cin >> q;
    int cnt = 1;
    for (int _q = 1; _q <= q; ++_q) {
        int l, r;
        cin >> l >> r;
        
        int res = 1;
        for (int i = l; i <= r; ++i) {
            auto [x, y] = segs[i];
            if (st.qry(x, y) == cnt) {
                res++;
                cnt++;
            }
            st.upd(x, y, cnt);
        }
        ++cnt;
        
        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:89:9: note: in expansion of macro 'debug'
   89 |         debug(segs[i]);
      |         ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 15628 KB Output is correct
2 Correct 217 ms 15280 KB Output is correct
3 Correct 219 ms 15256 KB Output is correct
4 Correct 242 ms 19124 KB Output is correct
5 Correct 233 ms 19912 KB Output is correct
6 Correct 31 ms 6868 KB Output is correct
7 Correct 36 ms 7124 KB Output is correct
8 Correct 38 ms 7112 KB Output is correct
9 Correct 41 ms 7088 KB Output is correct
10 Correct 45 ms 6860 KB Output is correct
11 Correct 148 ms 18888 KB Output is correct
12 Correct 136 ms 17864 KB Output is correct
13 Correct 140 ms 17716 KB Output is correct
14 Correct 155 ms 18880 KB Output is correct
15 Correct 160 ms 18376 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 33 ms 7204 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1069 ms 896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1028 ms 16012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 15628 KB Output is correct
2 Correct 217 ms 15280 KB Output is correct
3 Correct 219 ms 15256 KB Output is correct
4 Correct 242 ms 19124 KB Output is correct
5 Correct 233 ms 19912 KB Output is correct
6 Correct 31 ms 6868 KB Output is correct
7 Correct 36 ms 7124 KB Output is correct
8 Correct 38 ms 7112 KB Output is correct
9 Correct 41 ms 7088 KB Output is correct
10 Correct 45 ms 6860 KB Output is correct
11 Correct 148 ms 18888 KB Output is correct
12 Correct 136 ms 17864 KB Output is correct
13 Correct 140 ms 17716 KB Output is correct
14 Correct 155 ms 18880 KB Output is correct
15 Correct 160 ms 18376 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 33 ms 7204 KB Output is correct
18 Execution timed out 1069 ms 896 KB Time limit exceeded
19 Halted 0 ms 0 KB -