oj.uz

Submission #382907

# Submission time Handle Problem Language Result Execution time Memory
382907 2021-03-28T13:03:04 Z blacktulip Fountain (eJOI20_fountain) C++17
100 / 100
 477 ms 56612 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long lo;
typedef pair< lo,lo > PII;
 
#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define int long long
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
 
const lo inf = 1000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000007;
 
int n,m,b[li],a[li],k,flag,t,fa[li][30],sum[li][30],dp[li];
 
inline void build_lca(){
	for(int j=1;j<=27;j++){
		for(int i=1;i<=n;i++){
			fa[i][j]=fa[fa[i][j-1]][j-1];
			sum[i][j]=sum[i][j-1]+sum[fa[i][j-1]][j-1];
		}
	}
}
 
int32_t main(void){
	scanf("%lld %lld",&n,&t);
	FOR{
		scanf("%lld %lld",&a[i],&b[i]);
	}
	stack<pair<int,int>> st;
	for(int i=n;i>=1;i--){
		while(st.size() && st.top().fi<=a[i]){
			st.pop();
		}
		if(st.size())dp[i]=st.top().se;
		else dp[i]=n+1;
		st.push({a[i],i});
		//~ cout<<dp[i]<<" **\n";
	}
	FOR{
		fa[i][0]=dp[i];
		sum[i][0]=b[dp[i]];
	}
	build_lca();
	while(t--){
		int x,y;
		scanf("%lld %lld",&x,&y);
		if(b[x]>=y){printf("%lld\n",x);continue;}
		y-=b[x];
		//~ cout<<y<<" :: \n";
		for(int i=27;i>=0;i--){
			if(sum[x][i]<=y){
				y-=sum[x][i];
				x=fa[x][i];
				//~ cout<<y<<" :: \n";
			}
		}
		if(y!=0){
			for(int i=0;i<=27;i++){
				if(sum[x][i]>=y){
					y-=sum[x][i];
					x=fa[x][i];
					//~ cout<<y<<" :: \n";
					break;
				}
			}
		}
		if(y>0){
			printf("0\n");
			continue;
		}
		printf("%lld\n",x);
	}
	return 0;
}

Compilation message

fountain.cpp: In function 'int32_t main()':
fountain.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |  scanf("%lld %lld",&n,&t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
fountain.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%lld %lld",&a[i],&b[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
fountain.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%lld %lld",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 50028 KB Output is correct
2 Correct 345 ms 46572 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 2 ms 748 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 3 ms 876 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 876 KB Output is correct
8 Correct 329 ms 50028 KB Output is correct
9 Correct 345 ms 46572 KB Output is correct
10 Correct 2 ms 876 KB Output is correct
11 Correct 165 ms 30124 KB Output is correct
12 Correct 477 ms 56612 KB Output is correct
13 Correct 374 ms 54764 KB Output is correct
14 Correct 265 ms 53792 KB Output is correct
15 Correct 217 ms 54252 KB Output is correct