제출 #1199036

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199036		brover29	Osumnjičeni (COCI21_osumnjiceni)	C++17	0 / 110	1098 ms	59888 KiB

Main

#include <bits/stdc++.h>
//qwerty47924692
using namespace std;
using ll = long long;
const ll N=2e5+29;
const string br="617283";
#define sz(a)(ll)a.size()
#define f first
#define s second
ll n,l[N],r[N],dp[5005][5005],st[4*N],z[4*N];
map<ll,ll>mp;
set<ll>s;
void build(ll v,ll l,ll r){
    if(l==r){
        st[v]=0;
        return;
    }
    ll mid=(r+l)>>1;
    build(v*2,l,mid);
    build(v*2+1,mid+1,r);
    st[v]=0;
}void push(ll v,ll l,ll r){
    ll mid=(r+l)>>1;
    st[v*2]+=z[v]*(mid-l+1);
    st[v*2+1]+=z[v]*(r-mid);
    z[v*2]+=z[v];
    z[v*2+1]+=z[v];
    z[v]=0;
}
void update(ll v,ll l,ll r,ll x,ll y){
    if(l>y||x>r)return;
    if(x<=l&&r<=y){
        st[v]+=(r-l+1);
        z[v]++;
        return;
    }ll mid=(r+l)>>1;
    push(v,l,r);
    update(v*2,l,mid,x,y);
    update(v*2+1,mid+1,r,x,y);
    st[v]=st[v*2]+st[v*2+1];
}ll get(ll v,ll l,ll r,ll x,ll y){
    if(l>y||x>r)return 0;
    if(x<=l&&r<=y)return st[v];
    ll mid=(r+l)>>1;
    push(v,l,r);
    return get(v*2,l,mid,x,y)+get(v*2+1,mid+1,r,x,y);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        s.insert(l[i]);
        s.insert(r[i]);
    }ll timer=0;
    for(ll i:s){
        mp[i]=++timer;
    }for(ll i=1;i<=n;i++){
        l[i]=mp[l[i]];
        r[i]=mp[r[i]];
    }ll q;
    for(ll i=1;i<=n;i++){
        build(1,1,2*n);
        ll cnt=1;
        for(ll j=i;j<=n;j++){
            if(get(1,1,2*n,l[j],r[j])>=1){
                cnt++;
                build(1,1,2*n);
            }update(1,1,2*n,l[j],r[j]);
            dp[i][j]=cnt;
        }
    }
    cin>>q;
    while(q--){
        ll l,r;
        cin>>l>>r;
        cout<<dp[l][r]<<'\n';
    }
}

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