oj.uz

Submission #915412

# Submission time Handle Problem Language Result Execution time Memory
915412 2024-01-23T20:10:21 Z SalihSahin Osumnjičeni (COCI21_osumnjiceni) C++14
30 / 110
 1000 ms 52608 KB 
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
using namespace std;
 
const int mod = 998244353;

struct SEGT{
    vector<int> tree, lazy;

    void init(int n){
        tree.assign(4*n, 0);
        lazy.assign(4*n, 0);
    }

    void push(int ind){
        tree[ind*2] += lazy[ind];
        tree[ind*2+1] += lazy[ind];
        lazy[ind*2] += lazy[ind];
        lazy[ind*2+1] += lazy[ind];
        lazy[ind] = 0;
    }

    void update(int ind, int l, int r, int ql, int qr, int val){
        if(l > r || l > qr || r < ql) return;
        if(l == r){
            tree[ind] += val;
            lazy[ind] += val;
        }
        else{
            push(ind);
            int m = (l + r)/2;

            update(ind*2, l, m, ql, qr, val);
            update(ind*2+1, m+1, r, ql, qr, val);
            tree[ind] = max(tree[ind*2], tree[ind*2+1]);
        }
    }

    int query(int ind, int l, int r, int ql, int qr){
        if(l > r || l > qr || r < ql) return 0;
        if(l >= ql && r <= qr) return tree[ind];
        else{
            push(ind);
            int m = (l + r)/2;

            return max(query(ind*2, l, m, ql, qr),  query(ind*2+1, m+1, r, ql, qr));
        }
    }
};

int main(){
    int n;
    cin>>n;
    vector<pair<int, int> > a(n);
    set<int> ste;

    for(int i = 0; i < n; i++){
        int l, r;
        cin>>l>>r;
        ste.insert(l);
        ste.insert(r);
        a[i] = mp(l, r);
    }
    map<int, int> conv;
    int val = 1;
    for(auto itr: ste){
        conv[itr] = val;
        val++;
    }
    for(int i = 0; i < n; i++){
        a[i] = mp(conv[a[i].first], conv[a[i].second]);
    }
    int N = val + 5;
    
    SEGT seg;
    seg.init(N);
    vector<int> go(n);
    int r = 0;
    for(int l = 0; l < n; l++){
        while(r < n && seg.query(1, 1, N, a[r].first, a[r].second) == 0){
            seg.update(1, 1, N, a[r].first, a[r].second, 1);
            r++;
        }
        go[l] = r;

        seg.update(1, 1, N, a[l].first, a[l].second, -1);
    }
    int K = 18;

    vector<vector<int> > lift(K, vector<int>(n+1));
    for(int i = 0; i < n; i++){
        lift[0][i] = go[i];
    }
    lift[0][n] = n;

    for(int i = 1; i < K; i++){
        for(int j = 0; j <= n; j++){
            lift[i][j] = lift[i-1][lift[i-1][j]];
        }
    }

    int q;
    cin>>q;
    while(q--){
        int l, r;
        cin>>l>>r;
        int ans = 1;
        l--, r--;
        
        for(int i = K-1; i >= 0; i--){
            if(lift[i][l] <= r){
                l = lift[i][l];
                ans += (1 << i);
            }
        }

        cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 1872 KB Output is correct
2 Correct 401 ms 1900 KB Output is correct
3 Correct 413 ms 1912 KB Output is correct
4 Correct 428 ms 1944 KB Output is correct
5 Correct 391 ms 2128 KB Output is correct
6 Correct 11 ms 856 KB Output is correct
7 Correct 11 ms 856 KB Output is correct
8 Correct 11 ms 868 KB Output is correct
9 Correct 11 ms 840 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 16 ms 2116 KB Output is correct
12 Correct 15 ms 1884 KB Output is correct
13 Correct 18 ms 1880 KB Output is correct
14 Correct 17 ms 1884 KB Output is correct
15 Correct 18 ms 2136 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 11 ms 860 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 1872 KB Output is correct
2 Correct 401 ms 1900 KB Output is correct
3 Correct 413 ms 1912 KB Output is correct
4 Correct 428 ms 1944 KB Output is correct
5 Correct 391 ms 2128 KB Output is correct
6 Correct 11 ms 856 KB Output is correct
7 Correct 11 ms 856 KB Output is correct
8 Correct 11 ms 868 KB Output is correct
9 Correct 11 ms 840 KB Output is correct
10 Correct 11 ms 604 KB Output is correct
11 Correct 16 ms 2116 KB Output is correct
12 Correct 15 ms 1884 KB Output is correct
13 Correct 18 ms 1880 KB Output is correct
14 Correct 17 ms 1884 KB Output is correct
15 Correct 18 ms 2136 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 11 ms 860 KB Output is correct
18 Correct 733 ms 2984 KB Output is correct
19 Correct 678 ms 2640 KB Output is correct
20 Correct 752 ms 2892 KB Output is correct
21 Correct 702 ms 2664 KB Output is correct
22 Correct 682 ms 2636 KB Output is correct
23 Correct 299 ms 1440 KB Output is correct
24 Correct 317 ms 1456 KB Output is correct
25 Correct 358 ms 1840 KB Output is correct
26 Correct 322 ms 1616 KB Output is correct
27 Correct 307 ms 1468 KB Output is correct
28 Correct 291 ms 2324 KB Output is correct
29 Correct 339 ms 2416 KB Output is correct
30 Correct 307 ms 2388 KB Output is correct
31 Correct 316 ms 2384 KB Output is correct
32 Correct 298 ms 2404 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 305 ms 2164 KB Output is correct

Subtask #4
0 / 20.0

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

Subtask #5
0 / 50.0

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