oj.uz

Submission #466325

# Submission time Handle Problem Language Result Execution time Memory
466325 2021-08-18T15:53:31 Z spike1236 Fountain (eJOI20_fountain) C++14
100 / 100
 355 ms 27720 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ll long long
#define ld long double
#define all(_v) _v.begin(), _v.end()
#define sz(_v) (int)_v.size()
#define pii pair <int, int>
#define pll pair <ll, ll>
#define veci vector <int>
#define vecll vector <ll>

const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
const double PI = 3.1415926535897932384626433832795;
const double eps = 1e-9;
const int MOD1 = 1e9 + 7;
const int MOD2 = 998244353;

const int MAXN = 1e5 + 10;
int n, q;
int d[MAXN], c[MAXN];
int up[MAXN][20];
ll sum[MAXN][20];

void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n; ++i)
        cin >> d[i] >> c[i];
    stack <int> st;
    for(int i = n; i > 0; --i) {
        while(!st.empty() && d[st.top()] <= d[i]) st.pop();
        if(!st.empty()) up[i][0] = st.top();
        else up[i][0] = n + 1;
        sum[i][0] = c[i];
        st.push(i);
    }
    /**cout << "----------\n";
    for(int i = 1; i <= n; ++i) {
        cout << d[i] << ' ' << c[i] << ' ' << up[i][0] << '\n';
    }**/
    sum[n + 1][0] = 1e18;
    for(int j = 1; j < 19; ++j) {
        sum[n + 1][j] = 1e18;
        for(int i = 1; i <= n; ++i) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            sum[i][j] = sum[i][j - 1] + sum[up[i][j - 1]][j - 1];
        }
    }
    for(int cs = 1; cs <= q; ++cs) {
        ll v;
        int r;
        cin >> r >> v;
        for(int i = 18; i >= 0; --i) {
            if(sum[r][i] < v) {
                v -= sum[r][i];
                r = up[r][i];
            }
        }
        cout << (r == n + 1 ? 0 : r) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int CNT_TESTS = 1;
    ///cin >> CNT_TESTS;
    for(int NUMCASE = 1; NUMCASE <= CNT_TESTS; ++NUMCASE) {
        solve();
        if(NUMCASE != CNT_TESTS) cout << '\n';
    }
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 26016 KB Output is correct
2 Correct 239 ms 24388 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 456 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 2 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 226 ms 26016 KB Output is correct
9 Correct 239 ms 24388 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 101 ms 15980 KB Output is correct
12 Correct 355 ms 27720 KB Output is correct
13 Correct 223 ms 27460 KB Output is correct
14 Correct 186 ms 27396 KB Output is correct
15 Correct 173 ms 27324 KB Output is correct