Submission #1046240

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046240		Nickpapadak	Fountain (eJOI20_fountain)	C++14	60 / 100	1578 ms	5204 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);
}
// int mem[MAXN][MAXN];
// int solve(int i, int v){
// }

void solveqn(){
    int sol = 0;
    stack<int> stk;
    T[N+1] ={INF, 0};
    for(int i =1;i<=N+1;++i){
        while(!(stk.empty()) && T[i].X >= T[stk.top()].X){
            nb[stk.top()] =i;
            stk.pop();
        }stk.push(i);
    }
    T[0] = {0,INF};
    while(Q--){
        int a, b;
        scanf("%d%d", &a,&b);
        int prev = T[a].X-1;
        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");
    }
}

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:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:73:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
fountain.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d%d",&T[i].X, &T[i].Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~

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