Submission #999934

#	Time	Username	Problem	Language	Result	Execution time	Memory
999934		Br3ad	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	112 ms	8648 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;

int n;
vector<int> segTree(4*N); // Search by index

void build(int v, int tl, int tr, vector<pair<int, int>> &arr){
    if(tl == tr){
        segTree[v] = tl;
    }else {
        int tm = (tl + tr)/2;
        build(v*2, tl, tm, arr);
        build(v*2+1, tm+1, tr, arr);
        segTree[v] = (arr[segTree[v*2+1]].s >= arr[segTree[v*2]].s)? segTree[v*2+1] : segTree[v*2];
    }
}

void update(int v, int tl, int tr, int pos, vector<pair<int, int>> &arr){
    if(tl == tr && tl == pos){
        segTree[v] = n; // Means section used
    }else {
        int tm = (tl + tr)/2;
        if(pos <= tm) update(v*2, tl, tm, pos, arr);
        else update(v*2 + 1, tm+1, tr, pos, arr);
        segTree[v] = (arr[segTree[v*2+1]].s >= arr[segTree[v*2]].s)? segTree[v*2+1] : segTree[v*2];
    }
}

int query(int v, int tl, int tr, int l, int r, vector<pair<int, int>> &arr){
    if(l > r) return 0;
    if(tl == l && tr == r){
        return segTree[v];
    }else {
        int tm = (tl + tr)/2;

        int left = n, right = n;
        if(l <= tm) left = query(v*2, tl, tm, l, min(tm, r), arr);
        if(r >= tm + 1) right = query(v*2 + 1, tm + 1, tr, max(l, tm+1), r, arr);

        return (arr[right].s >= arr[left].s)? right : left;
    }
}

// Subtask 3
ll int plan_roller_coaster(vector<int> s, vector<int> t){
    n = s.size();
    vector<pair<int, int>> v;
    for(int i = 0; i < n; i++){
        v.PB(MP(t[i], s[i]));
    }

    sort(v.begin(), v.end());
    v[n] = MP(-inf, -inf);

    build(1, 0, n-1, v);

    pair<int, int> cur = v[n-1];
    update(1, 0, n-1, n-1, v);

    for(int i = 1; i < n; i++){
        // Find maximum s_next for eligible t_next
        int idx = upper_bound(v.begin(), v.end(), MP(cur.s, inf)) - v.begin() - 1;
        if(idx == -1) return 1; // No t smaller than current s

        int nxt = query(1, 0, n-1, 0, idx, v);
        if(nxt == n) return 1;

        update(1, 0, n-1, nxt, v);
        cur = v[nxt];
    }

    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});
//     cout << temp << endl;

//     temp = plan_roller_coaster({3, 4, 7, 4}, {2, 7, 3, 5});
//     cout << temp << endl;

//     temp = plan_roller_coaster({100, 5, 5}, {4, 1, 101});
//     cout << temp << endl;

//     temp = plan_roller_coaster({3, 5, 5, 6}, {5, 4, 5, 7});
//     cout << temp << endl;
// }

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

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