oj.uz

Submission #586417

# Submission time Handle Problem Language Result Execution time Memory
586417 2022-06-30T08:36:29 Z kideso Fountain (eJOI20_fountain) C++17
60 / 100
 1500 ms 6860 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 5472 KB Output is correct
2 Correct 76 ms 5536 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 328 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 66 ms 5472 KB Output is correct
9 Correct 76 ms 5536 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1137 ms 3304 KB Output is correct
12 Correct 91 ms 6860 KB Output is correct
13 Execution timed out 1571 ms 4372 KB Time limit exceeded
14 Halted 0 ms 0 KB -