Submission #931583

#	Time	Username	Problem	Language	Result	Execution time	Memory
931583		PieArmy	Fountain (eJOI20_fountain)	C++17	100 / 100	354 ms	52624 KiB

fountain

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n';
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}
#define int ll
struct Seg{
    int n;
    vector<int>tree;
    Seg(int N){
        n=N;
        tree.resize(n<<2,inf);
    }
    void update(int tar,int x){
        int node=1,left=0,right=n-1;
        while(left<right){
            tree[node]=min(tree[node],x);
            node<<=1;
            if(tar>mid){
                node++;
                left=mid+1;
            }
            else right=mid;
        }
        tree[node]=min(x,tree[node]);
    }
    int query(int l,int r,int node=1,int left=0,int right=-1){
        if(right==-1)right=n-1;
        if(left>r||right<l)return inf;
        if(left>=l&&right<=r)return tree[node];
        return min(query(l,r,node*2,left,mid),query(l,r,node*2+1,mid+1,right));
    }
};

void code(){
    int n,q;cin>>n>>q;
    int D[n+1],C[n+1];
    for(int i=1;i<=n;i++)
        cin>>D[i]>>C[i];
    D[0]=inf;C[0]=inf;
    int bin[n+1][20];
    int dis[n+1][20];
    for(int i=0;i<20;i++){
        bin[0][i]=0;
        dis[0][i]=inf;
    }
    map<int,int>mp;
    set<int>st={inf};
    for(int i=1;i<=n;i++)
        st.insert(D[i]);
    int las=0;
    for(int x:st)
        mp[x]=las++;
    Seg seg(las);
    seg.update(las-1,n+1);
    for(int i=n;i;i--){
        int ust=seg.query(mp[D[i]]+1,las-1);
        if(ust==n+1)ust=0;
        bin[i][0]=ust;
        for(int j=1;j<20;j++)
            bin[i][j]=bin[bin[i][j-1]][j-1];
        dis[i][0]=C[ust];
        for(int j=1;j<20;j++)
            dis[i][j]=min(inf,dis[i][j-1]+dis[bin[i][j-1]][j-1]);
        seg.update(mp[D[i]],i);
    }
    while(q--){
        int r,v;cin>>r>>v;
        if(v<=C[r]){
            cout<<r<<endl;continue;
        }
        int pos=r;
        v-=C[r];
        for(int i=19;i>=0;i--){
            if(dis[pos][i]>=v)continue;
            v-=dis[pos][i];
            pos=bin[pos][i];
        }
        pos=bin[pos][0];
        cout<<pos<<endl;
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
    int t=1;
    if(!t)cin>>t;
    while(t--){code();cout<<endl;}
    return 0;
}

Compilation message (stderr)

fountain.cpp: In function 'int32_t main()':
fountain.cpp:93:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~
fountain.cpp:93:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     bool usaco=0;if(usaco){freopen(".in","r",stdin);freopen(".out","w",stdout);}
      |                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~

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