oj.uz

Submission #588387

# Submission time Handle Problem Language Result Execution time Memory
588387 2022-07-03T08:51:41 Z dozer Fountain (eJOI20_fountain) C++14
100 / 100
 373 ms 35472 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define N 500005
#define pii pair<int, int>
#define st first
#define nd second
#define modulo 1000000007
#define LOGN 18
#define int long long

int nxt[LOGN][N], arr[N], c[N], sum[LOGN][N]; 

int32_t main()
{
	fastio();

	int n, q;
	cin>>n>>q;
	for (int i = 1; i <= n; i++)
		cin>>arr[i]>>c[i];
	arr[0] = modulo;
	nxt[0][n] = 0;
	for (int i = n - 1; i >= 1; i--)
	{
		nxt[0][i] = i + 1;
		while(arr[nxt[0][i]] <= arr[i]) nxt[0][i] = nxt[0][nxt[0][i]];
		sum[0][i] = c[nxt[0][i]];
		//cout<<i<<sp<<nxt[0][i]<<endl;
	}
	for (int i = 1; i < LOGN; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			sum[i][j] = sum[i - 1][j] + sum[i - 1][nxt[i - 1][j]];
			nxt[i][j] = nxt[i - 1][nxt[i - 1][j]];
			//cout<<i<<sp<<j<<sp<<sum[i][j]<<endl;
		}
	}

	while(q--)
	{
		int r, v;
		cin>>r>>v;
		if (v <= c[r])
		{
			cout<<r<<endl;
			continue;
		}
		v -= c[r];
		int curr = r;
		
		for (int i = LOGN - 1; i >= 0; i--)
		{
			int tmp = nxt[i][curr];
			if (tmp != 0 && sum[i][curr] <= v)
			{
				//cout<<curr<<sp<<v<<sp<<i<<sp<<tmp<<sp<<sum[i][curr]<<endl;
				v -= sum[i][curr];
				curr = tmp;
			}
		}
		if (v == 0) cout<<curr<<endl;
		else cout<<nxt[0][curr]<<endl;
	}
	

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 636 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 31836 KB Output is correct
2 Correct 253 ms 30552 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 636 KB Output is correct
2 Correct 1 ms 724 KB Output is correct
3 Correct 1 ms 852 KB Output is correct
4 Correct 2 ms 848 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 852 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 214 ms 31836 KB Output is correct
9 Correct 253 ms 30552 KB Output is correct
10 Correct 2 ms 856 KB Output is correct
11 Correct 89 ms 19372 KB Output is correct
12 Correct 373 ms 35472 KB Output is correct
13 Correct 242 ms 35056 KB Output is correct
14 Correct 145 ms 34440 KB Output is correct
15 Correct 119 ms 34716 KB Output is correct