oj.uz

Submission #553626

# Submission time Handle Problem Language Result Execution time Memory
553626 2022-04-26T12:25:16 Z czauderna Fountain (eJOI20_fountain) C++17
100 / 100
 346 ms 40012 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, 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].fs >> arr[i].sc;
	}
	nxt[n][0]=n; wg[n][0]=INF;
	stos[0].fs=n; stos[0].sc=INF;
	for(int i=n-1; i>=0; i--){
		while(arr[i].fs>=stos[idx].sc && idx>0) idx--;
		nxt[i][0]=stos[idx].fs; wg[i][0]=arr[i].sc;
		idx++;
		stos[idx].fs=i; stos[idx].sc =arr[i].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
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 228 ms 33812 KB Output is correct
2 Correct 275 ms 31240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 228 ms 33812 KB Output is correct
9 Correct 275 ms 31240 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 94 ms 21260 KB Output is correct
12 Correct 346 ms 40012 KB Output is correct
13 Correct 247 ms 38856 KB Output is correct
14 Correct 176 ms 37980 KB Output is correct
15 Correct 157 ms 38332 KB Output is correct