oj.uz

Submission #931583

# Submission time Handle Problem Language Result Execution time Memory
931583 2024-02-22T06:08:36 Z PieArmy Fountain (eJOI20_fountain) C++17
100 / 100
 354 ms 52624 KB 
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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 48688 KB Output is correct
2 Correct 266 ms 45356 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 860 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 1 ms 860 KB Output is correct
8 Correct 246 ms 48688 KB Output is correct
9 Correct 266 ms 45356 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 99 ms 23976 KB Output is correct
12 Correct 354 ms 52624 KB Output is correct
13 Correct 210 ms 43092 KB Output is correct
14 Correct 176 ms 39136 KB Output is correct
15 Correct 157 ms 51796 KB Output is correct