oj.uz

답안 #531644

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
531644 2022-03-01T07:44:43 Z wiwiho Railway Trip 2 (JOI22_ho_t4) C++14
11 / 100
 623 ms 96188 KB 
#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define ef(a) emplace_front(a)
#define pob pop_back()
#define pof pop_front()
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define tomax(a, b) ((a) = max((a), (b)))
#define tomin(a, b) ((a) = min((a), (b)))
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
using tiii = tuple<int, int, int>;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

ll ifloor(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a < 0) return (a - b + 1) / b;
    else return a / b;
}

ll iceil(ll a, ll b){
    if(b < 0) a *= -1, b *= -1;
    if(a > 0) return (a + b - 1) / b;
    else return a / b;
}

#define lc (2 * id + 1)
#define rc (2 * id + 2)

int n;

pii onion(pii a, pii b){
    return mp(min(a.F, b.F), max(a.S, b.S));
}

bool inside(pii r, int p){
    return r.F <= p && p <= r.S;
}

struct SegmentTree{
    
    vector<pii> st;

    void build(vector<pii>& v, int L = 1, int R = n, int id = 0){
        if(L == R){
            st[id] = v[L];
            return;
        }
        int M = (L + R) / 2;
        build(v, L, M, lc);
        build(v, M + 1, R, rc);
        st[id] = onion(st[lc], st[rc]);
    }

    pii query(int l, int r, int L = 1, int R = n, int id = 0){
        //assert(max(l, L) <= min(r, R));
        if(l <= L && R <= r) return st[id];
        int M = (L + R) / 2;
        if(r <= M) return query(l, r, L, M, lc);
        else if(l > M) return query(l, r, M + 1, R, rc);
        else return onion(query(l, r, L, M, lc), query(l, r, M + 1, R, rc));
    }

    void init(vector<pii>& v){
        st.resize(4 * n);
        build(v);
    }

};

int main(){
    StarBurstStream

    int K;
    cin >> n >> K;

    vector<vector<int>> el(n + 2), er(n + 2);
    int m;
    cin >> m;
    for(int i = 1; i <= m; i++){
        int a, b;
        cin >> a >> b;
        if(a < b){
            er[a].eb(b);
            er[min(n + 1, a + K)].eb(-b);
        }
        else{
            el[max(1, a - K + 1)].eb(b);
            el[a + 1].eb(-b);
        }
    }

    const int SZ = 20;
    vector<vector<pii>> go(SZ, vector<pii>(n + 1));
    multiset<int> sl, sr;
    for(int i = 1; i <= n; i++){
        for(int j : el[i]){
            if(j > 0) sl.insert(j);
            else sl.erase(sl.find(-j));
        }
        for(int j : er[i]){
            if(j > 0) sr.insert(j);
            else sr.erase(sr.find(-j));
        }
        int l = sl.empty() ? i : *sl.begin();
        int r = sr.empty() ? i : *sr.rbegin();
        assert(l <= r);
        go[0][i] = mp(l, r);
    }

    vector<SegmentTree> st(SZ);
    st[0].init(go[0]);
    //cerr << "test " << 0 << " ";
    //printv(go[0], cerr);
    for(int i = 1; i < SZ; i++){
        for(int j = 1; j <= n; j++){
            go[i][j] = st[i - 1].query(go[i - 1][j].F, go[i - 1][j].S);
        }
        st[i].init(go[i]);
        //cerr << "test " << i << " ";
        //printv(go[i], cerr);
    }

    int q;
    cin >> q;
    while(q--){

        int s, t;
        cin >> s >> t;

        if(!inside(go[SZ - 1][s], t)){
            cout << "-1\n";
            continue;
        }
        
        int ans = 0;
        pii now = mp(s, s);
        for(int i = SZ - 1; i >= 0; i--){
            pii nxt = st[i].query(now.F, now.S);
            if(!inside(nxt, t)){
                ans += 1 << i;
                now = nxt;
            }
        }
        
        cout << ans + 1 << "\n";
    }

    return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Runtime error 2 ms 588 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Runtime error 2 ms 588 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 315 ms 86300 KB Output is correct
2 Correct 326 ms 86268 KB Output is correct
3 Correct 314 ms 86376 KB Output is correct
4 Correct 295 ms 86144 KB Output is correct
5 Correct 278 ms 92700 KB Output is correct
6 Correct 357 ms 89548 KB Output is correct
7 Correct 199 ms 95128 KB Output is correct
8 Correct 221 ms 89240 KB Output is correct
9 Correct 179 ms 89536 KB Output is correct
10 Correct 377 ms 88908 KB Output is correct
11 Correct 338 ms 92852 KB Output is correct

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 86 ms 52996 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 450 ms 90756 KB Output is correct
2 Correct 623 ms 86808 KB Output is correct
3 Correct 579 ms 85200 KB Output is correct
4 Correct 577 ms 84244 KB Output is correct
5 Correct 452 ms 83856 KB Output is correct
6 Correct 489 ms 83556 KB Output is correct
7 Correct 336 ms 91616 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 8 ms 1996 KB Output is correct
10 Correct 373 ms 91168 KB Output is correct
11 Correct 386 ms 96188 KB Output is correct
12 Correct 391 ms 89840 KB Output is correct
13 Correct 472 ms 95356 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Runtime error 2 ms 1460 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Runtime error 2 ms 588 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -