oj.uz

답안 #913413

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
913413 2024-01-20T07:49:53 Z blackscreen1 Fountain (eJOI20_fountain) C++17
100 / 100
 524 ms 38656 KB 
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define ld long double
#define iloop(m, h) for (ll i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define iloop_(m, h, g) for (auto i = m; i != h; i += g)
#define jloop_(m, h, g) for (auto j = m; j != h; j += g)
#define kloop_(m, h, g) for (auto k = m; k != h; k += g)
#define lloop_(m, h, g) for (auto l = m; l != h; l += g)
#define getchar_unlocked _getchar_nolock // comment before submission
#define pll pair<ll, ll>
#define plll pair<ll, pll>
#define pllll pair<pll, pll>
#define vll vector<ll>
#define qll queue<ll>
#define dll deque<ll>
#define pqll priority_queue<ll>
#define gll greater<ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n, q;
	cin >> n >> q;
	ll d[n], c[n];
	iloop(0, n) cin >> d[i] >> c[i];
	ll twok[n][20], tot[n][20];
	memset(twok, -1, sizeof(twok));
	iloop(0, n) jloop(0, 20) tot[i][j] = INF;
	stack<ll> mono;
	iloop(n-1, -1) {
		while (mono.size() && d[mono.top()] <= d[i]) mono.pop();
		if (mono.size()) {
			twok[i][0] = mono.top();
			tot[i][0] = c[i] + c[twok[i][0]];
			jloop(1, 20) {
				if (twok[i][j-1] == -1) break;
				twok[i][j] = twok[twok[i][j-1]][j-1];
				if (twok[i][j] != -1) tot[i][j] = tot[i][j-1] + tot[twok[i][j-1]][j-1] - c[twok[i][j-1]];
			}
		}
		mono.push(i);
	}
	ll t1, t2;
	while (q--) {
		cin >> t1 >> t2;
		t1--;
		if (t2 <= c[t1]) {cout << t1+1 << "\n"; continue;}
		iloop(19, -1) {
			if (t1 == -1) break;
			if (t2 > tot[t1][i]) {
				t2 -= tot[t1][i] - c[twok[t1][i]];
				t1 = twok[t1][i];
			}
		}
		t1 = twok[t1][0];
		cout << t1+1 << "\n";
	}
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 336 ms 36036 KB Output is correct
2 Correct 292 ms 33556 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 732 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 336 ms 36036 KB Output is correct
9 Correct 292 ms 33556 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 90 ms 20676 KB Output is correct
12 Correct 524 ms 38656 KB Output is correct
13 Correct 247 ms 37712 KB Output is correct
14 Correct 165 ms 37008 KB Output is correct
15 Correct 148 ms 37184 KB Output is correct