oj.uz

답안 #791225

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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