oj.uz

Submission #369810

# Submission time Handle Problem Language Result Execution time Memory
369810 2021-02-22T13:04:00 Z AdamGS Fountain (eJOI20_fountain) C++14
100 / 100
 398 ms 39276 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 36204 KB Output is correct
2 Correct 294 ms 33772 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 748 KB Output is correct
5 Correct 2 ms 748 KB Output is correct
6 Correct 2 ms 748 KB Output is correct
7 Correct 2 ms 748 KB Output is correct
8 Correct 278 ms 36204 KB Output is correct
9 Correct 294 ms 33772 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 135 ms 20716 KB Output is correct
12 Correct 398 ms 39276 KB Output is correct
13 Correct 309 ms 37612 KB Output is correct
14 Correct 223 ms 36716 KB Output is correct
15 Correct 185 ms 36844 KB Output is correct