Submission #556915

#	Time	Username	Problem	Language	Result	Execution time	Memory
556915		new_acc	Osumnjičeni (COCI21_osumnjiceni)	C++14	110 / 110	609 ms	33720 KiB

Main

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=4e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=18;
pair<int,int> sorted[N],t[N];
int seg[(SS<<1)+10],lazy[(SS<<1)+10],nxt[N],jump[N][L+1];
void push(int v){
    lazy[(v<<1)]+=lazy[v],lazy[(v<<1)+1]+=lazy[v];
    seg[(v<<1)]+=lazy[v],seg[(v<<1)+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        seg[v]+=x,lazy[v]+=x;
        return;
    }
    push(v);
    upd(a,b,x,p,(p+k)>>1,(v<<1)),upd(a,b,x,((p+k)>>1)+1,k,(v<<1)+1);
    seg[v]=max(seg[(v<<1)],seg[(v<<1)+1]);
}
int Query(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return 0;
    if(p>=a and k<=b) return seg[v];
    push(v);
    return max(Query(a,b,p,(p+k)>>1,v<<1),Query(a,b,((p+k)>>1)+1,k,(v<<1)+1));
}
void solve(){
    int n;
    cin>>n;
    int curr=0;
    for(int a,b,i=1;i<=n;i++){
        cin>>a>>b;
        sorted[++curr]={a,i},sorted[++curr]={b,-i}; 
    }
    sort(sorted+1,sorted+1+curr);
    int l=0;
    for(int i=1;i<=curr;i++){
        if(sorted[i].fi!=sorted[i-1].fi or i==1) l++;
        if(sorted[i].se>0) t[sorted[i].se].fi=l;
        else t[sorted[i].se*(-1)].se=l;
    }
    curr=0;
    for(int i=1;i<=n;i++){
        curr=max(curr,i);
        while(curr<=n and Query(t[curr].fi,t[curr].se)==0){
            upd(t[curr].fi,t[curr].se,1);
            ++curr;
        }
        nxt[i]=curr;
        upd(t[i].fi,t[i].se,-1);
        jump[i][0]=nxt[i];
    }
    for(int i=0;i<=L;i++) jump[n+1][i]=n+1;
    for(int i=n;i>=1;i--)
        for(int k=1;k<=L;k++) jump[i][k]=jump[jump[i][k-1]][k-1];
    int q;
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        int res=1;
        for(int i=L;i>=0;i--)
            if(jump[a][i]<=b) res+=(1<<i),a=jump[a][i];
        cout<<res<<"\n";
    }
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

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