Submission #382904

#	Time	Username	Problem	Language	Result	Execution time	Memory
382904		blacktulip	Fountain (eJOI20_fountain)	C++17	0 / 100	318 ms	50304 KiB

fountain

#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";
			}
		}
		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 (stderr)

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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40