oj.uz

Submission #760789

# Submission time Handle Problem Language Result Execution time Memory
760789 2023-06-18T12:57:12 Z bachhoangxuan Fountain (eJOI20_fountain) C++17
100 / 100
 301 ms 10264 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define maxn 100005
const int inf=1e18;
const int bl=320;
int n,q,a[maxn],x[maxn],nxt[maxn],sum[maxn],sxt[maxn];
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i=1;i<=n;i++)cin >> a[i] >> x[i];
    a[n+1]=x[n+1]=inf;
    vector<int> Max;Max.push_back(n+1);
    for(int i=n;i>=1;i--){
        while(a[i]>=a[Max.back()]) Max.pop_back();
        nxt[i]=Max.back();Max.push_back(i);
    }
    for(int i=1;i<=n;i++){
        int u=i;
        for(int j=0;j<bl;j++){
            sum[i]+=x[u];
            if(u==n+1) break;
            else u=nxt[u];
        }
        sxt[i]=u;
    }
    for(int i=1;i<=q;i++){
        int r,v;cin >> r >> v;
        while(true){
            if(r==n+1) break;
            if(sum[r]<v){
                v-=sum[r];
                r=sxt[r];
            }
            else if(x[r]<v){
                v-=x[r];r=nxt[r];
            }
            else break;
        }
        if(r!=n+1) cout << r << '\n';
        else cout << 0 << '\n';
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 8532 KB Output is correct
2 Correct 210 ms 8524 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 203 ms 8532 KB Output is correct
9 Correct 210 ms 8524 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 102 ms 4940 KB Output is correct
12 Correct 301 ms 10264 KB Output is correct
13 Correct 236 ms 9308 KB Output is correct
14 Correct 63 ms 8296 KB Output is correct
15 Correct 51 ms 8532 KB Output is correct