Submission #674972

#	Time	Username	Problem	Language	Result	Execution time	Memory
674972		vjudge1	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	355 ms	54580 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("Ofast")
 
#define F first
#define S second
#define vi vector<int>
#define vvi vector<vi>
#define pi pair<int, int>
#define vpi vector<pi>
#define vb vector<bool>
#define vvb vector<vb>
#define pb push_back
#define ppb pop_back
#define read(a) for(auto &x:a) cin >> x;
#define print(a) for(auto x:a) cout << x << " "; cout << "\n";
#define vc vector<char>
#define vvc vector<vc>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
#define int long long
#define ld long double
const int INF = 1e18;
const int inf = 1e9;

const int N = 2e5+10, LOG = 20;
int l[N], r[N];
int st[N][LOG+1];
set<pi> s;
 
bool fit(int ix){
    if(s.empty()) return 1;

    auto it = s.lower_bound({l[ix], 0});
    pi c = (it == s.end() ? make_pair(INF, INF) : *it), p = (it == s.begin() ? make_pair(-INF, -INF) : *prev(it));

    if(r[ix] >= c.F || p.S >= l[ix]) return 0;
    return 1;
}

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

void solve(){
    int n; cin >> n;
    for(int i=0; i<n; i++)
        cin >> l[i] >> r[i];

    int ix = 0;
    for(int i=0; i<n; i++){
        s.insert({l[i], r[i]});
        ix = max(ix, i+1);
        while(ix < n && fit(ix)){
            s.insert({l[ix], r[ix]});
            ix++;
        }
        st[i][0] = ix;
        s.erase({l[i], r[i]});
    }
    for(int j=0; j<=LOG; j++)
        st[n][j] = n;

    for(int j=1; j<=LOG; j++)
    for(int i=0; i<n; i++)
        st[i][j] = st[st[i][j-1]][j-1];

    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        cout << query(l-1, r-1) << "\n";
    }
}
 
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    // #ifndef ONLINE_JUDGE
    //     freopen("in.txt", "r", stdin);
    //     freopen("out.txt", "w", stdout);
    // #endif
 
    int tt = 1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50