oj.uz

Submission #526746

# Submission time Handle Problem Language Result Execution time Memory
526746 2022-02-16T03:37:43 Z joelau Osumnjičeni (COCI21_osumnjiceni) C++14
10 / 110
 1000 ms 44804 KB 
#include <bits/stdc++.h>
using namespace std;

int N,Q;
pair<int,int> lst[200005];
vector<int> A;

struct node {
    int s,e,m,v,lazy; node *l, *r;
    node (int S, int E) {
        s = S, e = E, m = (s+e)/2, v = 0, lazy = -1;
        if (s != e) l = new node(s,m), r = new node(m+1,e);
    }
    void propo() {
        if (lazy == -1) return;
        v = lazy * (e-s+1);
        if (s != e) l->lazy = lazy, r->lazy = lazy;
        lazy = -1;
    }
    void update (int x, int y, int nv) {
        propo();
        if (s == x && e == y) lazy = nv;
        else {
            if (y <= m) l -> update(x,y,nv);
            else if (x > m) r -> update(x,y,nv);
            else l -> update(x,m,nv), r -> update(m+1,y,nv);
            l->propo(), r->propo();
            v = l->v + r->v;
        }
    }
    int query (int x, int y) {
        propo();
        if (s == x && e == y) return v;
        else if (y <= m) return l -> query(x,y);
        else if (x > m) return r -> query(x,y);
        else return l->query(x,m) + r->query(m+1,y);
    }
}*root;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N;
    for (int i = 0; i < N; ++i) {
        cin >> lst[i].first >> lst[i].second;
        A.push_back(lst[i].first); A.push_back(lst[i].second);
    }
    sort(A.begin(),A.end());
    A.resize(unique(A.begin(),A.end())-A.begin());
    for (int i = 0; i < N; ++i) {
        lst[i].first = lower_bound(A.begin(),A.end(),lst[i].first) - A.begin();
        lst[i].second = lower_bound(A.begin(),A.end(),lst[i].second) - A.begin();
    }
    root = new node(0,A.size()-1);
    cin >> Q;
    while (Q--) {
        int l,r; cin >> l >> r; l--, r--;
        root -> update(0,A.size()-1,0);
        int ans = 1;
        for (int i = l; i <= r; ++i) {
            if (root -> query(lst[i].first,lst[i].second) != 0) {
                ans++;
                root -> update(0,A.size()-1,0);
            }
            root -> update(lst[i].first,lst[i].second,1);
        }
        cout << ans << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 42812 KB Output is correct
2 Correct 509 ms 42184 KB Output is correct
3 Correct 500 ms 42268 KB Output is correct
4 Correct 548 ms 42788 KB Output is correct
5 Correct 559 ms 44732 KB Output is correct
6 Correct 44 ms 6804 KB Output is correct
7 Correct 70 ms 6816 KB Output is correct
8 Correct 53 ms 6968 KB Output is correct
9 Correct 60 ms 7080 KB Output is correct
10 Correct 63 ms 6712 KB Output is correct
11 Correct 283 ms 43192 KB Output is correct
12 Correct 270 ms 40632 KB Output is correct
13 Correct 269 ms 40492 KB Output is correct
14 Correct 306 ms 43336 KB Output is correct
15 Correct 291 ms 42164 KB Output is correct
16 Correct 0 ms 300 KB Output is correct
17 Correct 49 ms 7232 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1012 ms 1448 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 1012 ms 1448 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 1038 ms 44804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 553 ms 42812 KB Output is correct
2 Correct 509 ms 42184 KB Output is correct
3 Correct 500 ms 42268 KB Output is correct
4 Correct 548 ms 42788 KB Output is correct
5 Correct 559 ms 44732 KB Output is correct
6 Correct 44 ms 6804 KB Output is correct
7 Correct 70 ms 6816 KB Output is correct
8 Correct 53 ms 6968 KB Output is correct
9 Correct 60 ms 7080 KB Output is correct
10 Correct 63 ms 6712 KB Output is correct
11 Correct 283 ms 43192 KB Output is correct
12 Correct 270 ms 40632 KB Output is correct
13 Correct 269 ms 40492 KB Output is correct
14 Correct 306 ms 43336 KB Output is correct
15 Correct 291 ms 42164 KB Output is correct
16 Correct 0 ms 300 KB Output is correct
17 Correct 49 ms 7232 KB Output is correct
18 Execution timed out 1012 ms 1448 KB Time limit exceeded
19 Halted 0 ms 0 KB -