Submission #781046

#	Time	Username	Problem	Language	Result	Execution time	Memory
781046		cig32	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	757 ms	51240 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 4;
struct node{
    int upd, ans;
} a[4*MAXN];
void range_add(int l,int r,int constl,int constr,int idx,int val){
    if(l<=constl && constr<=r){
        a[idx].upd += val;
        a[idx].ans += (constr-constl+1) * val;
        return;
    }
    int mid = (constl + constr) >> 1;
    if(mid<l || r<constl) range_add(l, r, mid+1, constr, 2*idx+2, val);
    else if(constr<l || r<mid+1) range_add(l, r, constl, mid, 2*idx+1, val);
    else{
        range_add(l, r, constl, mid, 2*idx+1, val);
        range_add(l, r, mid+1, constr, 2*idx+2, val);
    }
    a[idx].ans = a[2*idx+1].ans + a[2*idx+2].ans + (constr-constl+1) * a[idx].upd;
}
int query_sum(int l,int r,int constl,int constr,int idx){
    if(l<=constl && constr<=r) return a[idx].ans;
    int mid = (constl + constr) >> 1;
    int sz = min(r, constr) - max(l, constl) + 1;
    if(mid<l || r<constl) return sz * a[idx].upd + query_sum(l, r, mid+1, constr, 2*idx+2);
    else if(constr<l || r<mid+1) return sz * a[idx].upd + query_sum(l, r, constl, mid, 2*idx+1);
    else{
        return sz * a[idx].upd + query_sum(l, r, constl, mid, 2*idx+1) + query_sum(l, r, mid+1, constr, 2*idx+2);
    }
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    int l[n+1], r[n+1];
    for(int i=1; i<=n; i++) cin >> l[i] >> r[i];
    int s[2*n];
    unordered_map<int, int> is;
    for(int i=1; i<=n; i++) {
        s[2*i-2] = l[i];
        s[2*i-1] = r[i];
    }
    sort(s, s+2*n);
    int it=0;
    for(int i=0; i<2*n; i++) {
        if(s[i] != s[i-1] || i == 0) is[s[i]] = ++it;
    }
    for(int i=1; i<=n; i++) {
        l[i] = is[l[i]];
        r[i] = is[r[i]];
    }
    int d[n+1];
    int lp = 1, rp = 1;
    range_add(l[1], r[1], 0, MAXN-1, 0, 1);
    while(!(lp == n && rp == n)) {
        d[lp] = rp;
        if(rp<n && query_sum(l[rp+1], r[rp+1], 0, MAXN-1, 0) == 0) {
            range_add(l[rp+1], r[rp+1], 0, MAXN-1, 0, 1);
            rp++;
        }
        else {
            range_add(l[lp], r[lp], 0, MAXN-1, 0, -1);
            lp++;
            if(rp < lp) {
                rp++;
                range_add(l[rp], r[rp], 0, MAXN-1, 0, 1);
            }
        }
    }
    d[n] = n;
    int st[18][n+2];
    for(int i=1; i<=n; i++) st[0][i] = d[i] + 1;
    st[0][n + 1] = n + 1;
    for(int i=1; i<18; i++) {
        for(int j=1; j<=n+1; j++) {
            st[i][j] = st[i-1][st[i-1][j]];
        }
    }
    int q0; cin >> q0;
    while(q0--) {
        int p, q; cin >> p >> q;
        int k = 32 - __builtin_clz(q-p+1) - 1;
        int ans = 0;
        for(int i=k; i>=0; i--) {
            if(st[i][p] <= q) {
                p = st[i][p];
                ans += (1<<i);
            }
        }
        while(p <= q) {
            ans++;
            p = d[p] + 1;
        }
        cout << ans << endl;
    }
}

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