Submission #1224810

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224810		minhpk	Fountain (eJOI20_fountain)	C++20	100 / 100	321 ms	41012 KiB

fountain

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a,b;
int bruh=1e16;
pair<int,int> z[1000005];
vector <int> v;
int par[100005][21];
int cost[100005][21];

pair<int,int> f[4000005];
void update(int id,int l,int r,int pos, pair<int,int>val){
     if (l==r){
        f[id]=val;
        return;
     }
     int mid=(l+r)/2;
     if (pos<=mid){
         update(id*2,l,mid,pos,val);
     }else{
         update(id*2+1,mid+1,r,pos,val);
     }
     if (f[id*2].second>f[id*2+1].second){
         f[id]=f[id*2];
     }else{
         f[id]=f[id*2+1];
     }

}
pair<int,int> get(int id,int l,int r,int x,int y){
    if (x>r || y<l){
        return {0,0};
    }
    if (l>=x && y>=r){
        return f[id];
    }
    int mid=(l+r)/2;
    pair<int,int> pre1=get(id*2,l,mid,x,y);
    pair<int,int> pre2=get(id*2+1,mid+1,r,x,y);
    if (pre1.second>pre2.second){
        return pre1;
    }else{
        return pre2;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a >> b;
    for (int i=1;i<=a;i++){
         cin >> z[i].first >> z[i].second;
         v.push_back(z[i].first);
    }
    z[a+1]={bruh,bruh};
    v.push_back(1e16);
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    int n=v.size();
    for (int i=1;i<=a+1;i++){
         z[i].first=lower_bound(v.begin(),v.end(),z[i].first)-v.begin()+1;
    }
    int cur=1;
    pair<int,int> pre1={a+1,cur};
    par[a+1][0]=a+1;
    cost[a+1][0]=0;
    update(1,1,n,z[a+1].first,pre1);
    for (int i=a;i>=1;i--){
         pair<int,int> pre=get(1,1,n,z[i].first+1,n);
         par[i][0]=pre.first;
         cost[i][0]=z[i].second;
         cur++;
         pre1={i,cur};
         update(1,1,n,z[i].first,pre1);
    }

    for (int j=1;j<=20;j++){
         for (int i=1;i<=a+1;i++){
              par[i][j]=par[par[i][j-1]][j-1];
              cost[i][j]=cost[i][j-1]+cost[par[i][j-1]][j-1];
         }
    }

    while (b--){
         int x,y;
         cin >> x >> y;
         int capacity=y;
         int cnt=0;
         int p=x;
         for (int i=20;i>=0;i--){
              if (cnt+cost[p][i]<capacity){
                  cnt+=cost[p][i];
                  p=par[p][i];
              }
         }
         if (p==a+1){
             cout << 0 << "\n";
             continue;
         }
         int remain=capacity-cnt;
         bool check=false;
        // cout << p << " ";
         if (p==a+1){
             cout << 0 << "\n";
             check=true;
         }
         if (!check){
             if (remain>z[p].second){
                 remain-=z[p].second;
                 p=par[p][0];
             }else{
                 cout << p << "\n";
                 check=true;
             }
             if (p==a+1){
                 cout << 0 << "\n";
                 check=true;
             }
         }

         if (!check){
             if (remain>z[p].second){
                 remain-=z[p].second;
                 p=par[p][0];
             }else{
                 cout << p << "\n";
                 check=true;
             }
             if (p==a+1){
                 cout << 0 << "\n";
                 check=true;
             }
         }

         if (!check){
             if (remain>z[p].second){
                 remain-=z[p].second;
                 p=par[p][0];
             }else{
                 cout << p << "\n";
                 check=true;
             }
             if (p==a+1){
                 cout << 0 << "\n";
                 check=true;
             }
         }
    }
    return 0;
}

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