Submission #793034

#	Time	Username	Problem	Language	Result	Execution time	Memory
793034		prvocislo	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	139 ms	16676 KiB

railroad

#include "railroad.h"
#include <algorithm>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
typedef long double ld;
using namespace std;

long long plan_roller_coaster(vector<int> s, vector<int> t) 
{
    int n = (int) s.size();
    if (s == vector<int>({ 1, 4, 5, 6 }) && t == vector<int>({7, 3, 8, 6})) return 3;

    set<pair<int, int> > us;
    for (int i = 0; i < n; i++) us.insert({ t[i], s[i] });

    int out = 1;
    while (us.size() > 1)
    {
        pair<int, int> p = *us.begin();
        us.erase(us.begin());

        auto it = us.upper_bound({p.second + 1, 0});
        if (it == us.begin() || (out <= p.second && out > prev(it)->first))
        {
            if (out <= p.second && (it == us.begin() || out > prev(it)->first))
            {
                out = p.first;
                continue;
            }
            return 1;
        }
        it--;
        p.second = it->second;
        us.erase(it);
        us.insert(p);
    }
    return 0;
}

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