제출 #1255041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1255041		__ugur__	Fountain (eJOI20_fountain)	C++20	30 / 100	1593 ms	1608 KiB

fountain

#include <iostream>
#include <cstdint>
#include <vector>
#include <stack>
#include <math.h>

using namespace std;

vector<int> diameters;      // D
vector<int> capacities;     // C
vector<int> next_drain;     // next higher, min D (like pointer)

int main() {

    int N, Q;
    cin >> N >> Q;
    diameters = vector<int>(N+1, 0);
    capacities = vector<int>(N+1, 0);
    next_drain = vector<int>(N+1, -1);
    for(int i=1; i<=N; i++) {
        int temp;
        cin >> temp;
        diameters[i] = temp;
        cin >> temp;
        capacities[i] = temp;
    }
    
    {
        stack<int> s;                   // next_drain'leri bulcazz
        for(int i=1; i<N; i++) {
            s.push(i);
            while(s.size() && (diameters[s.top()] < diameters[i+1])) {
                next_drain[s.top()] = i+1;
                s.pop();
            }
        }
    }

    while(Q--) {
        int start, vol;
        cin >> start >> vol;
        while(1) {
            vol -= capacities[start];
            if(vol > 0) {
                start = next_drain[start];
                if(start == -1) {
                    cout << "0\n";
                    goto next_query;
                }
                continue;
            }
            cout << start << '\n';
            goto next_query;
        }
        next_query:
        continue;
    }
    
    return 0;
}

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