oj.uz

Submission #553620

# Submission time Handle Problem Language Result Execution time Memory
553620 2022-04-26T12:17:20 Z czauderna Fountain (eJOI20_fountain) C++17
30 / 100
 243 ms 35692 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 464 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 35692 KB Output is correct
2 Correct 243 ms 33036 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 464 KB Output isn't correct
3 Halted 0 ms 0 KB -