oj.uz

Submission #724581

# Submission time Handle Problem Language Result Execution time Memory
724581 2023-04-15T15:09:16 Z TheSahib Osumnjičeni (COCI21_osumnjiceni) C++17
0 / 110
 172 ms 21328 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
#define ll long long
#define oo 1e9 + 9
#define pii pair<int, int>
 
using namespace std;

const int MAX = 2e5 + 5;

int n, q;
pii arr[MAX];

int st[20][MAX];

bool checkRange(pii a, pii b){
    return a.first <= b.second && a.second >= b.first;
}

void calcMaxR(){
    set<pii> s;
    int l = 0;
    for (int i = 0; i < n; i++)
    {
        while(!s.empty()){
            auto itr = s.upper_bound({arr[i].first, 0});
            auto itr2 = s.upper_bound({arr[i].second, 0});
            if(itr != s.begin()) --itr;
            if(itr2 != s.begin()) --itr2;
            if((checkRange(arr[i], (*itr))) || checkRange(arr[i], (*itr2))){
                st[0][l] = i;
                s.erase(arr[l]);
                ++l;
            }
            else{
                break;
            }
        }
        s.insert(arr[i]);
    }
    
    for (int j = l; j <= n; j++)
    {
        st[0][j] = n;
    }
}


void build(){
    for (int j = 1; j < 20; j++)
    {
        for (int i = 0; i <= n; i++)
        {
            st[j][i] = st[j - 1][st[j - 1][i]];
        }
    }
}

int ask(int l, int r){
    int ans = 1;
    for(int j = 19; j >= 0; --j){
        if(st[j][l] <= r){
            l = st[j][l];
            ans += (1 << j);
        }
    }
    return ans;
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i].first >> arr[i].second;
    }
    calcMaxR();
    build();

    cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        --l; --r;
        cout << ask(l, r) << '\n';
    }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16700 KB Output is correct
2 Correct 156 ms 20180 KB Output is correct
3 Correct 153 ms 20164 KB Output is correct
4 Correct 161 ms 20428 KB Output is correct
5 Correct 171 ms 21328 KB Output is correct
6 Correct 147 ms 19496 KB Output is correct
7 Incorrect 152 ms 19812 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 852 KB Output is correct
2 Correct 13 ms 968 KB Output is correct
3 Correct 15 ms 996 KB Output is correct
4 Correct 16 ms 996 KB Output is correct
5 Correct 13 ms 952 KB Output is correct
6 Correct 14 ms 1000 KB Output is correct
7 Incorrect 13 ms 964 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 852 KB Output is correct
2 Correct 13 ms 968 KB Output is correct
3 Correct 15 ms 996 KB Output is correct
4 Correct 16 ms 996 KB Output is correct
5 Correct 13 ms 952 KB Output is correct
6 Correct 14 ms 1000 KB Output is correct
7 Incorrect 13 ms 964 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 17384 KB Output is correct
2 Correct 172 ms 21036 KB Output is correct
3 Correct 151 ms 19564 KB Output is correct
4 Correct 147 ms 19352 KB Output is correct
5 Correct 156 ms 19992 KB Output is correct
6 Correct 151 ms 19688 KB Output is correct
7 Incorrect 146 ms 19480 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 16700 KB Output is correct
2 Correct 156 ms 20180 KB Output is correct
3 Correct 153 ms 20164 KB Output is correct
4 Correct 161 ms 20428 KB Output is correct
5 Correct 171 ms 21328 KB Output is correct
6 Correct 147 ms 19496 KB Output is correct
7 Incorrect 152 ms 19812 KB Output isn't correct
8 Halted 0 ms 0 KB -