oj.uz

Submission #1043666

# Submission time Handle Problem Language Result Execution time Memory
1043666 2024-08-04T13:14:57 Z Nickpapadak Fountain (eJOI20_fountain) C++14
0 / 100
 1500 ms 1548 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+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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Execution timed out 1591 ms 1548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

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