oj.uz

Submission #908450

# Submission time Handle Problem Language Result Execution time Memory
908450 2024-01-16T12:22:32 Z Tyx2019 Fountain (eJOI20_fountain) C++17
100 / 100
 607 ms 9756 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

main(){
    int N,Q;
    cin >> N >> Q;
    int D[N+5],C[N+5];
    for(int i=1;i<=N;i++) cin >> D[i] >> C[i];
    stack<int> stek;
    int next[N+5];
    for(int i=N;i>=1;i--){
        if(!stek.empty()){
            while(!stek.empty()){
                if(D[stek.top()]<=D[i]) stek.pop();
                else break;
            }
        }
        if(stek.empty()) next[i]=0;
        else next[i]=stek.top();
        stek.push(i);
    }
    const int blksize=300;
    int squirtloc[N];
    int squirtsum[N];
    for(int i=1;i<=N;i++){
        squirtsum[i]=0;
        int cur=i;
        for(int k=0;k<blksize;k++){
            squirtsum[i]+=C[cur];
            cur=next[cur];
            if(cur==0) break;
        }
        squirtloc[i]=cur;
    }
    for(int i=0;i<Q;i++){
        int resevoir, amtofwater;
        cin >> resevoir >> amtofwater;
        int cur=resevoir;
        for(int i=0;i<2*blksize;i++){
            if(cur==0){
                break;
            }
            if(amtofwater<=squirtsum[cur]){
                break;
            }
            else{
                amtofwater-=squirtsum[cur];
                cur=squirtloc[cur];
            }
        }
        if(cur==0){
            cout << "0\n";
            continue;
        }
        int prev=-1;
      //  cout << amtofwater << ' ';
        if(amtofwater>C[cur]){
			//cout << "YEY\n";
			amtofwater-=C[cur];
			for(int i=0;i<10*blksize;i++){
				if(cur==0){
					break;
				}
				if(amtofwater>C[next[cur]]){
					amtofwater-=C[next[cur]];
					cur=next[cur];
					//cout << cur << " ";
				} 
				else break;
			}
			cout << next[cur] << "\n";
		}
		else{
			cout << cur << "\n";
		}
    }
    //for(int i=1;i<=N;i++) cout << next[i] << " ";
    //cout << "\n";
    //for(int i=1;i<=N;i++) cout << squirtsum[i] << " ";
}

Compilation message

fountain.cpp:5:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    5 | main(){
      | ^~~~
fountain.cpp: In function 'int main()':
fountain.cpp:56:13: warning: unused variable 'prev' [-Wunused-variable]
   56 |         int prev=-1;
      |             ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 8452 KB Output is correct
2 Correct 446 ms 7860 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 5 ms 344 KB Output is correct
7 Correct 4 ms 348 KB Output is correct
8 Correct 415 ms 8452 KB Output is correct
9 Correct 446 ms 7860 KB Output is correct
10 Correct 6 ms 348 KB Output is correct
11 Correct 239 ms 4700 KB Output is correct
12 Correct 607 ms 9756 KB Output is correct
13 Correct 538 ms 8632 KB Output is correct
14 Correct 372 ms 8176 KB Output is correct
15 Correct 359 ms 8220 KB Output is correct