제출 #851671

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851671		pomuchle	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	257 ms	30928 KiB

railroad

#include "railroad.h"
#ifdef DEBUG
#include <cstdio>
#include <cassert>
int main() {
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}
#endif

#include <ios>
#include <vector>
#include <functional>
#include <set>
#include <cassert>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, p, n) for(int i=(p); i<=(n); ++i)
#define V std::vector
#define sz(A) (int(A.size()))
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef V <bool> vb;
ll plan_roller_coaster(vi s, vi t) {
    int n = sz(s);
    vb czy(n, 0);
    struct ziom{
        int o,w,i;
        ziom(){}
        ziom(int no, int nw, int ni){o=no,w=nw,i=ni;}
        ziom(int j){o=w=i=j;}
    };
    V <ziom> z(n);
    REP(i, n)
        z[i]={s[i], t[i], i};
    auto ogrcmp=[](const ziom &i, const ziom &j){return i.o<j.o;};
    auto wyjcmp=[](const ziom &i, const ziom &j){return i.w<j.w;};
    std::multiset <ziom, decltype(ogrcmp)> os(ogrcmp);
    std::multiset <ziom, decltype(wyjcmp)> ws(wyjcmp);
    os.insert(z.begin(), z.end());
    ws.insert(z.begin(), z.end());
    ziom l=z[0],p=l;
    czy[0]=1;
    while (1){ // dodajemy z prawej
        auto itr=os.upper_bound(ziom(p.w));
        while (itr!=os.begin()&&czy[std::next(itr, -1)->i])
            --itr,itr=os.erase(itr);
        if (itr==os.begin())
            break;
        --itr;
        p=*itr;
        os.erase(itr);
        czy[p.i]=1;
    }
    while (1){ // dodajemy z lewej
        auto itr=ws.upper_bound(l.o);
        while (itr!=ws.begin()&&czy[std::next(itr, -1)->i])
            --itr,itr=ws.erase(itr);
        if (itr==ws.begin())
            break;
        --itr;
        l=*itr;
        ws.erase(itr);
        czy[l.i]=1;
    }
    REP(i, n)
        if (!czy[i])
            return 1;
    return 0;
}

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