Submission #553620

#	Time	Username	Problem	Language	Result	Execution time	Memory
553620		czauderna	Fountain (eJOI20_fountain)	C++17	30 / 100	243 ms	35692 KiB

fountain

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fs first
#define sc second
const int LIM = 1e5+3, LG=21, INF=1e9+5;
long long idx, nxt[LIM][LG], wg[LIM][LG];
pair<int, pair<int, int>> arr[LIM], stos[LIM];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	long long n, q, a, b, o, t;
	cin >> n >> q;
	for(int i=0; i<n; i++){
		cin >> arr[i].sc.fs >> arr[i].sc.sc;
		arr[i].fs=i;
	}	
	nxt[n][0]=n; wg[n][0]=INF;
	stos[0].fs=n; stos[0].sc.fs=INF; stos[0].sc.sc=INF;
	for(int i=n-1; i>=0; i--){
		while(arr[i].sc.fs>stos[idx].sc.fs && idx>0) idx--;
		nxt[arr[i].fs][0]=stos[idx].fs; wg[arr[i].fs][0]=arr[i].sc.sc;
		idx++;
		stos[idx].fs=arr[i].fs; stos[idx].sc.fs =arr[i].sc.fs;
	}
	for(int i=1; i<LG; ++i){
        for(int j=0; j<=n; j++){
        	nxt[j][i]=nxt[nxt[j][i-1]][i-1];
        	wg[j][i]+=wg[nxt[j][i-1]][i-1]+wg[j][i-1];
        }
    }
    for(int i=0; i<q; i++){
    	cin >> a >> b; --a;
    	for(int k=LG-1; k>=0; k--){
    		if(b-wg[a][k]>0){
    			b-=wg[a][k];
    			a=nxt[a][k];
    		}
    	}
    	cout << (a+1)%(n+1) << "\n";
    }
}

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:12:24: warning: unused variable 'o' [-Wunused-variable]
   12 |  long long n, q, a, b, o, t;
      |                        ^
fountain.cpp:12:27: warning: unused variable 't' [-Wunused-variable]
   12 |  long long n, q, a, b, o, t;
      |                           ^

• Subtask 1: 0 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40