oj.uz

Submission #531639

# Submission time Handle Problem Language Result Execution time Memory
531639 2022-03-01T07:37:24 Z wiwiho Railway Trip 2 (JOI22_ho_t4) C++14
11 / 100
 2000 ms 97204 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){
        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();
        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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Execution timed out 2056 ms 316 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Execution timed out 2056 ms 316 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 87140 KB Output is correct
2 Correct 276 ms 87156 KB Output is correct
3 Correct 306 ms 87524 KB Output is correct
4 Correct 260 ms 87016 KB Output is correct
5 Correct 253 ms 94880 KB Output is correct
6 Correct 306 ms 91796 KB Output is correct
7 Correct 186 ms 97204 KB Output is correct
8 Correct 169 ms 90324 KB Output is correct
9 Correct 135 ms 90644 KB Output is correct
10 Correct 371 ms 91276 KB Output is correct
11 Correct 277 ms 95056 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2050 ms 30384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 378 ms 90932 KB Output is correct
2 Correct 548 ms 86896 KB Output is correct
3 Correct 499 ms 85296 KB Output is correct
4 Correct 492 ms 84292 KB Output is correct
5 Correct 383 ms 83876 KB Output is correct
6 Correct 469 ms 83576 KB Output is correct
7 Correct 300 ms 91748 KB Output is correct
8 Correct 2 ms 460 KB Output is correct
9 Correct 6 ms 2128 KB Output is correct
10 Correct 363 ms 91464 KB Output is correct
11 Correct 382 ms 96232 KB Output is correct
12 Correct 400 ms 90168 KB Output is correct
13 Correct 451 ms 95436 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Execution timed out 2062 ms 828 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 460 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 544 KB Output is correct
4 Execution timed out 2056 ms 316 KB Time limit exceeded
5 Halted 0 ms 0 KB -