Submission #999866

#	Time	Username	Problem	Language	Result	Execution time	Memory
999866		Br3ad	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	163 ms	12956 KiB

railroad

#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <numeric>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define ull unsigned long long
#define f first
#define s second
#define PF push_front
#define PB push_back
#define MP make_pair
#define max(a, b) ((a > b)? a : b)
#define min(a, b) ((a < b)? a : b)
#define max3(a, b, c) max(max(a, b), c)
#define min3(a, b, c) min(min(a, b), c)

const int N = 2e5 + 5;
const int M = 1e9 + 7; 
const int inf = 0x3f3f3f3f;
const ll int INF = 1e18;

/*
Problem statement:
 - Each node: speed limit(s_i), exit speed(t_i)
 - Edge: Track length(x)

Edge Weight: max(t_cur - s_next, 0)
 
Subtask 3:
 - At node i, for all s_next >= t_cur, choose min/max(t_next)

Subtask 4:
 - 
*/

// Subtask 3
ll int plan_roller_coaster(vector<int> s, vector<int> t){
    multiset<pair<int, int>> node; // <speed_limit, exit_speed>
    for(int i = 0; i < s.size(); i++){
        node.insert(MP(t[i], s[i]));
    }

    pair<int, int> cur = *(--node.end());
    node.erase(node.find(cur));

    while(!node.empty()){
        auto it = node.upper_bound(MP(cur.s, inf));
        if(it == node.begin()) return 1;

        it--;
        cur = *it;
        it = node.upper_bound(MP(cur.f, 0));
        cur = *it;
        node.erase(it);
    }

    return 0;
}

// int main(){
    
//     ios::sync_with_stdio(false);
//     cin.tie(NULL);
    
//     // ifstream cin();
//     // ofstream cout();
    
//     int temp;
//     temp = plan_roller_coaster({1, 4, 5, 6}, {7, 3, 8, 6});
//     // temp = plan_roller_coaster({3, 4, 7, 4}, {2, 7, 3, 5});
//     // temp = plan_roller_coaster({100, 5, 5}, {4, 1, 101});
//     cout << temp << endl;
// }

/*
1: (100, 4)
2: (5, 1)
3: (5, 101)

1: (100, 1)
2: (5, 101) //terminate

*/

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 0 / 30
• Subtask 4: 0 / 36