oj.uz

Submission #791225

# Submission time Handle Problem Language Result Execution time Memory
791225 2023-07-23T18:25:33 Z otarius Fountain (eJOI20_fountain) C++17
100 / 100
 197 ms 26252 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
#include <stack>
using namespace std;

#define ff first
#define sc second
#define pb push_back
#define ll long long
#define pll pair<ll, ll>
#define pii pair <int, int>
#define ull unsigned long long

// #define int long long
// #define int unsigned long long

const ll inf = 1e9 + 7;
const ll weirdMod = 998244353;

int n, q;
ll sum[100005][17];
int par[100005][17];
int binDrop(int v, int sm) {
    for (int i = 16; i >= 0; i--) {
        if (par[v][i] != -1 && sum[v][i] < sm) {
            sm -= sum[v][i]; v = par[v][i];
        }
    }
    return v;
}
void solve() {
    cin >> n >> q;
    vector<pii> arr(n + 1);
    memset(par, -1, sizeof par);
    for (int i = 1; i <= n; i++)
        cin >> arr[i].ff >> arr[i].sc;
    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        while (!stk.empty() && arr[stk.top()].ff < arr[i].ff) {
            par[stk.top()][0] = i; sum[stk.top()][0] = arr[stk.top()].sc; stk.pop();
        }
        stk.push(i);
    }
    while (!stk.empty()) {
        par[stk.top()][0] = 0;
        sum[stk.top()][0] = arr[stk.top()].sc;
        stk.pop();
    }
    for (int j = 1; j <= 16; j++) {
        for (int i = 1; i <= n; i++) {
            if (par[i][j - 1] != -1 && par[par[i][j - 1]][j - 1] != -1) {
                par[i][j] = par[par[i][j - 1]][j - 1];
                sum[i][j] = sum[i][j - 1] + sum[par[i][j - 1]][j - 1];
            }
        }
    }
    int d, v;
    while (q--) {
        cin >> d >> v;
        cout << binDrop(d, v) << '\n';
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 24012 KB Output is correct
2 Correct 150 ms 23168 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6868 KB Output is correct
2 Correct 3 ms 6996 KB Output is correct
3 Correct 3 ms 6996 KB Output is correct
4 Correct 4 ms 7128 KB Output is correct
5 Correct 4 ms 7124 KB Output is correct
6 Correct 3 ms 7124 KB Output is correct
7 Correct 3 ms 7124 KB Output is correct
8 Correct 128 ms 24012 KB Output is correct
9 Correct 150 ms 23168 KB Output is correct
10 Correct 3 ms 7124 KB Output is correct
11 Correct 51 ms 17016 KB Output is correct
12 Correct 197 ms 26252 KB Output is correct
13 Correct 137 ms 25892 KB Output is correct
14 Correct 90 ms 25148 KB Output is correct
15 Correct 78 ms 25868 KB Output is correct