oj.uz

Submission #884948

# Submission time Handle Problem Language Result Execution time Memory
884948 2023-12-08T17:54:00 Z vjudge1 Fountain (eJOI20_fountain) C++17
100 / 100
 253 ms 58832 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define endl '\n'
#define ll long long
#define int ll
#define pii pair <int, int>
#define pb push_back
#define all(v) v.begin(), v.end()
#define F first
#define S second
#define io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define M_PI 3.14159265358979323846

const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const int INF = 1e18;

int n, q, x, y;
int a[N], b[N], sm[N][20], par[N][20];
vector<int> v[N];

void DFS(int node){
    for(int i = 1; i < 20; i++){
        par[node][i] = par[par[node][i - 1]][i - 1];
        sm[node][i] = sm[node][i - 1] + sm[par[node][i - 1]][i - 1];
    }
    for(int i : v[node]){
        par[i][0] = node;
        sm[i][0] = b[i];
        DFS(i);
    }
}

signed main() {
    io;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
    }
    stack<pii> s;
    s.push({INF, 0});
    for(int i = n; i > 0; i--){
        while(!s.empty() && s.top().first <= a[i]){
            s.pop();
        }
        int cur = s.top().second;
        v[cur].pb(i);
        s.push({a[i], i});
    }
    DFS(0);
    while(q--){
        cin >> x >> y;
        for(int i = 19; i >= 0; i--){
            if(sm[x][i] < y){
              //  cout << x << " " << y << " ----- " << sm[x][i] << "  ";
                y -= sm[x][i];
                x = par[x][i];

            }
        }
        cout << x << endl;
    }
}
/*
1 2 3 4 5 6     7
4 6 3 4 10 4    INF

5
8
9
12
16


0
101110
*/

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 54868 KB Output is correct
2 Correct 169 ms 52052 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 3 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 11108 KB Output is correct
6 Correct 3 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 163 ms 54868 KB Output is correct
9 Correct 169 ms 52052 KB Output is correct
10 Correct 3 ms 11096 KB Output is correct
11 Correct 65 ms 32644 KB Output is correct
12 Correct 253 ms 58832 KB Output is correct
13 Correct 130 ms 50772 KB Output is correct
14 Correct 108 ms 48784 KB Output is correct
15 Correct 92 ms 48072 KB Output is correct