Submission #420505

#	Time	Username	Problem	Language	Result	Execution time	Memory
420505		Peti	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	158 ms	8100 KiB

railroad

#include <bits/stdc++.h>
#include "railroad.h"

using namespace std;

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int) s.size();

    vector<int> compr;
    compr.reserve(2*n);
    for(int x : s)
        compr.push_back(x);
    for(int x : t)
        compr.push_back(x);

    sort(compr.begin(), compr.end());
    compr.erase(unique(compr.begin(), compr.end()), compr.end());

    vector<int> va(n), vb(n);
    for(int i = 0; i < n; i++){
        va[i] = lower_bound(compr.begin(), compr.end(), s[i])-compr.begin();
        vb[i] = lower_bound(compr.begin(), compr.end(), t[i])-compr.begin();
    }

    int m = (int)compr.size();
    vector<int> fok(m);
    for(int i = 0; i < n; i++){
        fok[va[i]]++;
        fok[vb[i]]--;
    }

    fok[0]--;
    fok[m-1]++;

    for(int i = 0; i < m-1; i++)
        fok[i+1] += fok[i];

    if(fok[m-1] == 0)
        return 1;
    return 0;
}

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