Submission #1255278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255278		__ugur__	Fountain (eJOI20_fountain)	C++20	30 / 100	4 ms	584 KiB

fountain

#include <iostream>
#include <cstdint>

using namespace std;

int diameters[10005];      // D
int capacities[10005];     // C
int next_drain[10006];     // next higher, min D (like pointer)
int stack[10002];

int main() {

    {
        diameters[0] = 0;
        capacities[0] = 0;
        uint64_t* ptr = (uint64_t*) next_drain;
        for(register register_t x=0; x<5003; x++)
            ptr[x] = -1;
    }
    int N, Q;
    cin >> N >> Q;

    
    {
        int ptr = 0;
        for(int i=1; i<=N; i++) {
            int d, c;
            cin >> d >> c;
            diameters[i] = d;
            capacities[i] = c;

            i--;
            int next = diameters[i+1];
            if(diameters[i] < next)
                next_drain[i] = i+1;
            else
                stack[ptr++] = i;
            while(ptr && diameters[stack[ptr-1]] < next) {
                next_drain[stack[ptr-1]] = i+1;
                ptr--;
            }
            i++;
        }
    }

    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";
                    break;
                }
                continue;
            }
            cout << start << '\n';
            break;
        }
    }
    
    return 0;
}
//6 5 4 10 6 8 3 5 4 14 10 9 4 20 1 25 6 30 5 8 3 13 2 8

Compilation message (stderr)

fountain.cpp: In function 'int main()':
fountain.cpp:17:33: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   17 |         for(register register_t x=0; x<5003; x++)
      |                                 ^

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