oj.uz

Submission #851656

# Submission time Handle Problem Language Result Execution time Memory
851656 2023-09-20T10:36:55 Z pomuchle Roller Coaster Railroad (IOI16_railroad) C++17
0 / 100
 248 ms 35024 KB 
#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, 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, 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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 1 ms 344 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Incorrect 1 ms 344 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 1 ms 344 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Incorrect 1 ms 344 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 31056 KB n = 199999
2 Correct 248 ms 34640 KB n = 199991
3 Incorrect 196 ms 35024 KB answer is not correct: 0 instead of 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB n = 2
2 Correct 0 ms 344 KB n = 2
3 Correct 0 ms 344 KB n = 2
4 Correct 1 ms 344 KB n = 2
5 Correct 0 ms 344 KB n = 2
6 Incorrect 1 ms 344 KB answer is not correct: 0 instead of 523688153
7 Halted 0 ms 0 KB -