oj.uz

답안 #467279

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
467279 2021-08-22T11:58:29 Z syrtin Fountain (eJOI20_fountain) C++17
30 / 100
 342 ms 50544 KB 
/*author:	syrtin*/
#include <bits/stdc++.h>

#define pb push_back
#define all(v) v.begin(),v.end()
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair < int, int > pii;
typedef vector<int> vi;
typedef vector<long long> vll;

const int N = 1e6 + 1;
const ll MOD = 1e9 + 7;
const int inf = int(1e9);
const ll INF = ll(1e16);

void SOLVE(/*WATLE*/) {
	int n, q;
	cin >> n >> q;
	ll c[n], d[n];
	pll go[n + 4][32];
	stack<int> s;
	for(int i = 0; i < n; i++) {
		cin >> d[i] >> c[i];
	}
	for(int i = 0; i < 32; i++) go[n - 1][i] = {n + 1, c[n - 1]}, go[n + 1][i] = {n + 1, 0};
	s.push(n - 1);
	for(int i = n - 2; i >= 0; i--) {
		while(!s.empty() && d[i] > d[s.top()]) {
			s.pop();
		}
		if(!s.empty()){
			go[i][0] = {s.top(), c[i]};
			for(int o = 1; o < 32; o++) go[i][o] = {go[go[i][o - 1].ff][o - 1].ff, go[i][o - 1].ss + go[go[i][o - 1].ff][o - 1].ss};
		}
		else for(int o = 0; o < 32; o++) go[i][o] = {n + 1, c[i]};
		s.push(i);
	}
	while(q--) {
		ll j, x;
		cin >> j >> x;
		if(go[j - 1][31].ss < x)cout << 0 << '\n';
		else {
			j--;
			while(go[j][0].ss < x) {
				for(int o = 31; o >= 0; o--) {
					if(go[j][o].ss < x) {
						x -= go[j][o].ss, j = go[j][o].ff;
						break;
					}
				}
			}
			cout << j + 1 << '\n';
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
    int times = 1;
	//cin >> times;
    for(int i = 1; i <= times; i++) {
        //cout << "Case #" << t << ": ";
        SOLVE();
    }
    return 0;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 311 ms 50544 KB Output is correct
2 Correct 342 ms 46624 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 460 KB Output isn't correct
3 Halted 0 ms 0 KB -