Submission #464733

#	Time	Username	Problem	Language	Result	Execution time	Memory
464733		jurgis	Fountain (eJOI20_fountain)	C++14	0 / 100	78 ms	4924 KiB

fountain

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+1;
int t[2*maxn];
 int n, q;
void build(){
    for(int i =n-1; i>0;i--){
        t[i] = t[i<<1] + t[i<<1|1];
    }
}
ll query(int l, int r){
    ll res = 0;
    for(l+=n, r+=n; l<r; r>>=1, l>>=1){
        if(l&1){res+= t[l++];}
        if(r&1){res+= t[--r];}
    }
    return res;
}

int main()
{
   cin>>n>>q; ll d[n+1], c[n+1], r[q], v[q];bool secondsub = true; int mx;
    for(int i=1; i<=n; i++){
        cin>>d[i]>>c[i];
        t[i+n-1] = c[i];
        if(i==1){ mx = d[i];}
        else{
                if(mx>= d[i]){
                    secondsub = false;
                }
                else{
                    mx = d[i];
                }
        }
        }

    if(!secondsub){
        for(int i=0; i<q;i++){cin>>r[i]>>v[i];}
        for(int i =0;i <q; i++){
        int pab = r[i]; int paskd = d[r[i]];v[i] -= c[r[i]];
            while(pab!= n+1 && v[i] >0){

                if(paskd<d[pab]){
                    //cout<<"alip";
                    v[i] -= c[pab];
                    paskd = d[pab];
                }
                //cout<<"pask d " <<paskd<<" "<<pab<<" v[i] "<<v[i]<<endl;
                if(v[i] >0){
                    pab++;
                }

        }
        if(pab ==n+1){cout<<0<<"\n";}
        else{cout<<pab<<"\n";}
        }
    }
    else{
          //  cout<<"working";
        for(int i=0; i<q; i++){
            int lo =1; int hi= n+1;
            while(lo<hi){
                int mid = (lo+hi)/2;
                if(query(hi-1, mid-1) < v[i]){
                    lo = mid+1;
                }
                else{
                    hi = mid;
                }
            }
            if(lo == n+1){
                cout<<0<<"\n";
            }
            else{
                cout<<lo-1<<"\n";
            }

        }
    }


}

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