oj.uz

Submission #675957

# Submission time Handle Problem Language Result Execution time Memory
675957 2022-12-28T15:38:55 Z Kubeti Fountain (eJOI20_fountain) C++14
60 / 100
 323 ms 5148 KB 
#include <iostream>
#include <vector>
#include <stack>
#define nmax 100000
using namespace std;
struct fountain{
    int l, d;
} v[nmax + 5];
int ans[nmax+5], smen[nmax + 5], n, q;
void build(){
    stack<int> s;
    for(int i=1; i<=n; i++){
        if(s.size() == 0)
            s.push(i);
        else{
            while(!s.empty() && v[i].l > v[s.top()].l){
                ans[s.top()] = i;
                s.pop();
            }
            
            s.push(i);
        }
    }
    while(!s.empty()){
        ans[s.top()] = -1;
        s.pop();
    }
    
}
int main() {
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>v[i].l>>v[i].d;
    }
    if(n <= 2000){
        build();
        for(int t=0; t<q; t++){
            int l, i, ok = true;
            cin>>i>>l;
            while(true){
                l -= v[i].d;
                if(l <= 0)
                    break;
                if(i == -1){
                    ok = false;
                    break;
                }
                i = ans[i];
            }
            cout<<max(i, ok)<<endl;
        }
    }
    else{
        for(int i=1; i<=n; i++){
            smen[i] = smen[i-1] + v[i].d;
        }
        for(int t=0; t<q; t++){
            int l, i;
            cin>>i>>l;
            int st=i, dr=n+1;
            while(st<dr){
                int mid = (st+dr)/2;
                if(smen[mid] - smen[i-1] < l)
                    st = mid + 1;
                else dr = mid;
            }
            if(dr == n+1)
                cout<<0<<'\n';
            else cout<<dr<<'\n';
        }
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 3280 KB Output is correct
2 Correct 323 ms 5148 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 212 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 3 ms 212 KB Output is correct
5 Correct 6 ms 212 KB Output is correct
6 Correct 7 ms 212 KB Output is correct
7 Correct 4 ms 280 KB Output is correct
8 Correct 302 ms 3280 KB Output is correct
9 Correct 323 ms 5148 KB Output is correct
10 Correct 4 ms 320 KB Output is correct
11 Incorrect 199 ms 3208 KB Output isn't correct
12 Halted 0 ms 0 KB -