oj.uz

Submission #1043659

# Submission time Handle Problem Language Result Execution time Memory
1043659 2024-08-04T13:05:17 Z Nickpapadak Fountain (eJOI20_fountain) C++14
0 / 100
 25 ms 1644 KB 
#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;++i) nb[i] = N+1;
    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);
        }
    }
    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);
        }
        if(a == N+1) printf("0\n");
        else 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)){
        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

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

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 1644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -