Submission #1043666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043666		Nickpapadak	Fountain (eJOI20_fountain)	C++14	0 / 100	1591 ms	1548 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 = val - sf[i];
    return max(0, ans);
}
// int ans[MAXN];
int nb[MAXN];
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 && a != N+1){ // T[nb[a]].Y
            a = nb[a];
            b -= T[a].Y;
            // printf("%d  ", b);
        }
        printf("%d\n", a);
    }
    // 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) && 1 ==2){
    //     for(int i = N;i >=1; --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:37:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         scanf("%d%d", &a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
fountain.cpp: In function 'int main()':
fountain.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d",&N,&Q);
      |     ~~~~~^~~~~~~~~~~~~~
fountain.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%d%d",&T[i].X, &T[i].Y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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