oj.uz

Submission #774146

# Submission time Handle Problem Language Result Execution time Memory
774146 2023-07-05T12:21:40 Z Dzadzo Fountain (eJOI20_fountain) C++17
100 / 100
 362 ms 36896 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF INT_MAX
#define MOD 1000000009
#define MAXN 100000
using namespace std;
int p[MAXN+1][21];
int sum[MAXN+1];
vvi adj(MAXN+1);
void dfs(int v,int par,int c[]){
	if (par==-1)sum[v]=0;else sum[v]=sum[par]+c[v];
	p[v][0]=par;
	for (int i=1;i<=20;i++){
		if (p[v][i-1]<1)continue;
		p[v][i]=p[p[v][i-1]][i-1];
	}
	
	for (int u:adj[v])if (u!=par)dfs(u,v,c);
}
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	int d[n+1],c[n+1];
	for (int i=1;i<=n;i++)cin>>d[i]>>c[i];
	int next[n+1];
	stack<pii> s;
	for (int i=n;i>=1;i--){
		while (!s.empty() && s.top().F<=d[i])s.pop();
		if (s.empty())next[i]=0; else next[i]=s.top().S;	
		s.push({d[i],i});
	}
	
	for (int i=1;i<=n;i++){
		adj[next[i]].pb(i);
		adj[i].pb(next[i]);
	}
	memset(p,-1,sizeof(p));
	dfs(0,-1,c);
	while (q--){
		int v,vol;
		cin>>v>>vol;
		if (c[v]>=vol)cout<<v<<"\n";else{
			int cur=v;
			for (int i=20;i>=0;i--){
				if (p[cur][i]==-1 || p[cur][i]==0)continue;
				if (sum[v]-sum[p[p[cur][i]][0]]<vol)cur=p[cur][i];
			}
			cout<<p[cur][0]<<"\n";
		}
	}
}

Compilation message

fountain.cpp:27:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   27 | main() {
      | ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Output is correct
2 Correct 8 ms 19156 KB Output is correct
3 Correct 9 ms 19080 KB Output is correct
4 Correct 8 ms 19208 KB Output is correct
5 Correct 8 ms 19156 KB Output is correct
6 Correct 8 ms 19208 KB Output is correct
7 Correct 8 ms 19216 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 269 ms 31740 KB Output is correct
2 Correct 362 ms 30920 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19020 KB Output is correct
2 Correct 8 ms 19156 KB Output is correct
3 Correct 9 ms 19080 KB Output is correct
4 Correct 8 ms 19208 KB Output is correct
5 Correct 8 ms 19156 KB Output is correct
6 Correct 8 ms 19208 KB Output is correct
7 Correct 8 ms 19216 KB Output is correct
8 Correct 269 ms 31740 KB Output is correct
9 Correct 362 ms 30920 KB Output is correct
10 Correct 9 ms 19156 KB Output is correct
11 Correct 87 ms 25560 KB Output is correct
12 Correct 246 ms 36896 KB Output is correct
13 Correct 197 ms 31476 KB Output is correct
14 Correct 129 ms 29940 KB Output is correct
15 Correct 88 ms 30460 KB Output is correct