oj.uz

Submission #1043750

# Submission time Handle Problem Language Result Execution time Memory
1043750 2024-08-04T15:59:17 Z Nickpapadak Fountain (eJOI20_fountain) C++14
60 / 100
 1500 ms 6736 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 = 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

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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 2092 KB Output is correct
2 Correct 50 ms 2128 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 40 ms 2092 KB Output is correct
9 Correct 50 ms 2128 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 993 ms 3144 KB Output is correct
12 Correct 63 ms 6736 KB Output is correct
13 Execution timed out 1537 ms 3536 KB Time limit exceeded
14 Halted 0 ms 0 KB -