Submission #908450

#	Time	Username	Problem	Language	Result	Execution time	Memory
908450		Tyx2019	Fountain (eJOI20_fountain)	C++17	100 / 100	607 ms	9756 KiB

fountain

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

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