Submission #586417

#	Time	Username	Problem	Language	Result	Execution time	Memory
586417		kideso	Fountain (eJOI20_fountain)	C++17	60 / 100	1571 ms	6860 KiB

fountain

#include <iostream>
#include <queue>

using namespace std;

struct P {
    int d, v, n;
};

vector <P> x;
int N, Q;
bool ok = true;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> N >> Q;

    x.assign(N + 1, { 0,0,0 });

    for (int i = 1; i <= N; ++i) {
        cin >> x[i].d >> x[i].v;
        if (x[i].d <= x[i - 1].d) ok = false;
    }

    if (ok) {
        vector<int> t(N + 1, 0);
        for (int i = 1; i <= N; ++i)
            t[i] = t[i - 1] + x[i].v;

        int ind, vol;

        while (Q--) {
            cin >> ind >> vol;

            auto it = lower_bound(t.begin(), t.end(), vol + t[ind - 1]);

            if (it == t.end()) cout << 0;
            else cout << it - t.begin();

            cout << '\n';
        }
    }
    else {
        x[N].n = N + 1;
        for (int i = N - 1; i >= 1; --i) {
            int j = i + 1;
            while (j != N + 1 && x[i].d >= x[j].d) {
                j = x[j].n;
            }

            x[i].n = j;
        }

        int ind, vol;
        while (Q--) {
            cin >> ind >> vol;

            int ans = ind;
            while (ans != N + 1 && vol > 0) {
                vol -= x[ans].v;
                if (vol > 0) ans = x[ans].n;
            }

            if (ans == N + 1) cout << 0;
            else cout << ans;

            cout << '\n';
        }
    }

    return 0;
}

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