Submission #1309514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309514		zadniprovska	Fountain (eJOI20_fountain)	C++20	60 / 100	406 ms	589824 KiB

fountain

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
 
const ll DIM = 1e5 + 7;
const ll INF = 1e9;
const ll mod = 998244353;
const ll maxlog = 20;
const ll bsize = 350;

ll d[DIM], c[DIM], nxt[DIM];
bool flag[DIM];
vector<ll> s[DIM], v[DIM];
ll path[DIM], pos[DIM];

void solve() {

    ll n, nq;
    cin >> n >> nq;

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

        nxt[i] = 0;
        flag[i] = 1;
    }
    c[0] = INF;

    stack<ll> st;
    for (int i=1; i<=n; i++) {
        
        while (!st.empty() && d[st.top()] < d[i]) {
            nxt[st.top()] = i;

            flag[i] = 0;

            st.pop();
        }

        st.push(i);

    }

    ll cnt = 0;
    for (int i=1; i<=n; i++) {
        if (!flag[i]) continue;

        cnt++;
        ll cur = i, sum = 0;
        s[cnt].pb(0);
        v[cnt].pb(-1);
        do {

            sum += c[cur];
            s[cnt].pb(sum);
            v[cnt].pb(cur);

            path[cur] = cnt; pos[cur] = s[cnt].size() - 1;

            cur = nxt[cur];

        } while (cur != 0);
    }

    for (int i=1; i<=cnt; i++) {

        v[i].pb(0);
        s[i].pb(s[i][s[i].size()-1] + c[0]);

    }

    for (int i=1; i<=nq; i++) {

        ll r, vol;
        cin >> r >> vol;

        ll need = s[path[r]][pos[r]-1] + vol;

        ll it = lower_bound(s[path[r]].begin(), s[path[r]].end(), need) - s[path[r]].begin();

        cout << v[path[r]][it] << endl;

    }

}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("atlarge.in", "r", stdin);
    //freopen("atlarge.out", "w", stdout);
 
    int ntest = 1;
    //cin >> ntest;
    while (ntest--) {
        solve();
    }
    return 0;
 
}
;

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