Submission #1207113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1207113		smathewih	Fountain (eJOI20_fountain)	C++17	100 / 100	178 ms	22672 KiB

fountain

#include<bits/stdc++.h>

// task dependent stuff
#define STANDARD 1
#define INTERACTIVE 0
#define OUTPUTONLY 2

#define TASKTYPE STANDARD
#if TASKTYPE > 0
#define endl '\n'
#endif

// common functions/members
#define X first
#define Y second
#define pb push_back
#define mkp make_pair

// some basic ahh for macros
#define FORT for(int tii=0;tii<t;tii++)

using namespace std;
const int mod = 1000000007;
const int huge = 1000000000;
const int big = 20000000;

typedef long long ll;
typedef std::pair<int, int> pii;

int n, q;
int d[200007];
int c[200007];
int up[200007][20];
vector<int> con[200007];

void presum(int i, int par) {
    c[i] += c[par];
    up[i][0] = par;
    for (int l = 1; l < 20; l++) {
        up[i][l] = up[up[i][l - 1]][l - 1];
    }
    for (int j = 0; j < con[i].size(); j++) {
        presum(con[i][j], i);
    }
}

// dont forget to set task type!
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> d[i] >> c[i];

    priority_queue<pii, vector<pii>, greater<pii>> minp;
    for (int i = 0; i < n; i++) {
        if (!minp.empty()) {
            while (minp.top().X < d[i]) {
                con[i].pb(minp.top().Y);
                minp.pop();
                if (minp.empty()) break;
            }
        }
        minp.push(mkp(d[i], i));
    }
    while (!minp.empty()) {
        con[n].pb(minp.top().Y);
        minp.pop();
    }
    c[n] = 0;
    presum(n, n);
    int a, b;
    for (int i = 0; i < q; i++) {
        cin >> a >> b; a--; // a is the STUPID fountain bowl thing and b is WATEH IN LITEHRSY
        for (int l = 19; l != -1; l--) {
            int dif = c[a] - c[up[a][l]];
            if (dif < b) {
                b -= dif;
                a = up[a][l];
            }
        }
        a++;
        if (a == (n + 1)) cout << 0 << endl;
        else cout << a << endl;
    }
    /*cout << "TIS THE GRAPH\n";
    for (int i = 0; i <= n; i++) {
        cout << i + 1 << " :";
        for (int j = 0; j < con[i].size(); j++) {
            cout << " " << con[i][j] + 1;
        }
        cout << endl;
    }
    cout << "MY DAD LEFT ME (PARENTS)\n";
    for (int i = 0; i <= n; i++) {
        cout << i + 1 << " :";
        for (int j = 0; j < 20; j++) {
            cout << " " << up[i][j] + 1;
        }
        cout << endl;
    }*/

    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40