oj.uz

Submission #641986

# Submission time Handle Problem Language Result Execution time Memory
641986 2022-09-18T07:00:24 Z Kanimet0 Fountain (eJOI20_fountain) C++17
30 / 100
 179 ms 18928 KB 
#include<bits/stdc++.h>
using namespace std;
typedef int 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;
	for (int i = 0; i < n; i++) 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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 17140 KB Output is correct
2 Correct 179 ms 18928 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -