Submission #373962

#	Time	Username	Problem	Language	Result	Execution time	Memory
373962		FEDIKUS	Fountain (eJOI20_fountain)	C++17	100 / 100	578 ms	51296 KiB

fountain

#include <bits/stdc++.h>
#define mp make_pair
#define xx first
#define yy second
#define pb push_back

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pii;

vector<ll> sparsemax[19];
vector<ll> logovi;
vector<vector<ll> > g;
vector<ll> tren;
vector<ll> lift[19];
vector<ll> sume;
vector<bool> bio;
vector<pii> niz;

ll query(ll l,ll r){
    //cout<<l<<" "<<r<<" "<<logovi[r-l+1]<<" "<<l+(1<<logovi[r-l+1])<<" "<<max(sparsemax[logovi[r-l+1]][r],sparsemax[logovi[r-l+1]][l+(1<<logovi[r-l+1])-1])<<"\n";
    return max(sparsemax[logovi[r-l+1]][r],sparsemax[logovi[r-l+1]][l+(1<<logovi[r-l+1])-1]);
}

void dfs(ll cvor,ll sum){
    if(bio[cvor]) return;
    //cout<<cvor<<endl;
    sum+=niz[cvor].yy;
    //cout<<cvor<<" "<<niz[cvor].yy<<" "<<sum<<"\n";
    bio[cvor]=true;
    tren.push_back(cvor);
    for(ll i:g[cvor]){
        if(bio[i]) continue;
        dfs(i,sum);
    }
    //cout<<"proso"<<endl;
    for(ll i=0;i<19;i++){
        if((1<<i)>=tren.size()) {lift[i][cvor]=-1; continue;}
        lift[i][cvor]=tren[(ll)tren.size()-((ll)1<<i)-1];
    }

    sume[cvor]=sum;
    tren.pop_back();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n,q;
    cin>>n>>q;
    niz.resize(n+1);
    niz[n]=mp(1e9+1,1e9+1);
    for(ll i=0;i<n;i++) {cin>>niz[i].xx>>niz[i].yy;}
    logovi.resize(n+1);
    ll sta=-1;
    ll tren=1;
    for(ll i=1;i<=n;i++){
        if(tren==i){
            tren=2*i;
            sta++;
        }
        logovi[i]=sta;
    }
    g.resize(n+1);
    for(ll i=0;i<19;i++){
        sparsemax[i].resize(n+1);
        for(ll j=(1<<i)-1;j<=n;j++){
            if(i==0) sparsemax[i][j]=niz[j].xx;
            else{
                sparsemax[i][j]=max(sparsemax[i-1][j],sparsemax[i-1][j-((ll)1<<(i-1))]);
                //cout<<i<<" "<<j<<" "<<sparsemax[i][j]<<endl;
            }
        }
    }
    for(ll i=0;i<n;i++){
        ll l=i;
        ll r=n;
        ll naj=-1;
        while(l<=r){
            ll mid=l+(r-l)/2;
            //cout<<i<<" "<<mid<<" "<<query(i+1,mid)<<endl;
            if(query(i,mid)>niz[i].xx){
                naj=mid;
                r=mid-1;
            }else l=mid+1;
        }
        //cout<<i<<" "<<naj<<endl;
        g[i].pb(naj);
        g[naj].pb(i);
    }
    sume.resize(n+1);
    bio.resize(n+1,false);
    for(ll i=0;i<19;i++) lift[i].resize(n+1);
    dfs(n,0);
    //for(ll i=0;i<=n;i++) cout<<sume[i]<<" ";
    while(q--){
        ll r,v;
        cin>>r>>v;
        r--;
        ll tren=r;
        for(ll i=18;i>=0;i--){
            if(lift[i][tren]==-1) continue;
            if(sume[r]-sume[lift[i][tren]]>=v) continue;
            tren=lift[i][tren];
        }
        if(tren==n) cout<<0<<"\n";
        else cout<<tren+1<<"\n";
    }
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'void dfs(ll, ll)':
fountain.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if((1<<i)>=tren.size()) {lift[i][cvor]=-1; continue;}
      |            ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40