Submission #1043750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043750		Nickpapadak	Fountain (eJOI20_fountain)	C++14	60 / 100	1537 ms	6736 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
const unsigned int MAXN = 1e+5 +10;
const unsigned int INF = 1+9 + 10;
pair<int, int> T[MAXN];//  (diam, capacity)
int sf[MAXN]; 
int N, Q;
int solvesort(int i, int val){
    // int ans = i;
    T[0] = {0,0};
    int s = sf[i-1];
    int l = i, r = N;
    int mid = (l+r)>>1;
    // printf("%d - %d < %d\n", sf[N], s, val);
    if(sf[N] - s < val) return 0;
    while(l<r){
        if(sf[mid] - s >=val && sf[mid-1] - s < val) return mid;
        if(sf[mid]- s > val){
            r = mid-1;
            mid = (l+r)>>1;
        }else{
            l=mid+1;
            mid = (l+r)>>1;
        }
    }
    return l;
}
// int ans[MAXN];
int nb[MAXN];
int findlast(int i, int q){
    if(i == N+1) return 0;
    if(q <= T[i].Y) return i;
    return findlast(nb[i], q-T[i].Y);
}

void solveqn(){
    int sol = 0;
    stack<int> stk;
    T[N+1] ={INF, 0};
    for(int i =1;i<=N+1;++i){
        if(!(stk.empty())&&T[stk.top()].X > T[i].X){
            stk.push(i);
        }else{
            while(!(stk.empty()) && T[i].X >= T[stk.top()].X){
                nb[stk.top()] =i;
                stk.pop();
            }stk.push(i);
        }
    }
    T[0] = {0,INF};
    // ans[N+1] = 0;
    // for(int i = N; i >= 1; --i){
    //     ans[i] = ans[nb[i]] + T[i].Y;
    // }
    while(Q--){
        int a, b;
        scanf("%d%d", &a,&b);
        // b-=T[a].Y;
        // while(b > 0){ // T[nb[a]].Y
        //     a = nb[a];
        //     b -= T[a].Y;
        //     // printf("%d  ", b);
        // }
        int prev = T[a].X-1;
        // b -= T[a].Y;
        bool found = false;
        for(int i = a; i<=N && !found; ++i){
            if(prev < T[i].X){
                prev = T[i].X;
                b -= T[i].Y;
                sol = i;
            }
            if(b <=0){
                found = true;
            }
        }
        if(found) printf("%d\n", sol);
        else      printf("0\n");
        // printf("%d\n", findlast(a,b));
    }
    // return max(0, sol);
}

int main(){
    scanf("%d%d",&N,&Q);
    for(int i = 1;i <=N; ++i){
        scanf("%d%d",&T[i].X, &T[i].Y);
    }
    if(is_sorted(T+1,T+N+1)){
        for(int i = 1;i <=N; ++i){
            sf[i] = sf[i-1] + T[i].Y;
        }
        while(Q--){
            int a, b;
            scanf("%d%d",&a,&b);
            printf("%d\n", solvesort(a,b));
        }
    }else{
        solveqn();
    }
}

Compilation message (stderr)

fountain.cpp: In function 'void solveqn()':
fountain.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
fountain.cpp:89:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |         scanf("%d%d",&T[i].X, &T[i].Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~

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