Submission #369810

#	Time	Username	Problem	Language	Result	Execution time	Memory
369810		AdamGS	Fountain (eJOI20_fountain)	C++14	100 / 100	398 ms	39276 KiB

fountain

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
const int LIM=1e5+7, LG=20;
const ll INF=1e9+7;
ll c[LIM], nxt[LIM][LG], sum[LIM][LG];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll n, q;
	cin >> n >> q;
	rep(i, n) cin >> c[i] >> sum[i][0];
	sum[n][0]=c[n]=INF;
	nxt[n][0]=n;
	stack<pair<ll,ll>>s;
	s.push({c[n], n});
	for(int i=n-1; i>=0; --i) {
        while(s.top().st<=c[i]) s.pop();
        nxt[i][0]=s.top().nd;
        s.push({c[i], i});
	}
	for(int i=1; i<LG; ++i) {
        rep(j, n) {
            nxt[j][i]=nxt[nxt[j][i-1]][i-1];
            sum[j][i]=sum[j][i-1]+sum[nxt[j][i-1]][i-1];
        }
	}
	while(q--) {
        ll r, v;
        cin >> r >> v; --r;
        for(int i=LG-1; i>=0; --i) {
            if(v>sum[r][i]) {
                v-=sum[r][i];
                r=nxt[r][i];
            }
        }
        cout << (r+1)%(n+1) << '\n';
	}
}

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