oj.uz

Submission #701820

# Submission time Handle Problem Language Result Execution time Memory
701820 2023-02-22T07:10:59 Z jiahng Railway Trip 2 (JOI22_ho_t4) C++14
16 / 100
 2000 ms 368672 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int ll
typedef pair<int,int> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 400010
#define INF (ll)1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;
#define DEBUG 0

struct node{
    int s,e,m,mx,mn,lazy_mx=-INF,lazy_mn=INF;
    node *l,*r;

    node(int ss,int ee){
        s = ss; e = ee; m = (s + e) / 2;
        mx = e; mn = s;
        if (s != e){
             l = new node(s,m); r = new node(m+1,e);
        }
    }
    void prop(){
        if (s == e) return;
        l->lazy_mx = max(l->lazy_mx, lazy_mx);
        r->lazy_mx = max(r->lazy_mx, lazy_mx);
        l->mx = max(l->mx, lazy_mx);
        r->mx = max(r->mx, lazy_mx);

        l->lazy_mn = min(l->lazy_mn, lazy_mn);
        r->lazy_mn = min(r->lazy_mn, lazy_mn);
        l->mn = min(l->mn, lazy_mn);
        r->mn = min(r->mn, lazy_mn);

        lazy_mn = INF, lazy_mx = -INF;
    }

            
    void upd_mx(int a,int b,int c){
        prop();
        if (a <= s && e <= b){
            mx = max(mx, c);
            lazy_mx = max(lazy_mx, c);
        }else if (a > e || s > b) return;
        else{
            l->upd_mx(a,b,c); r->upd_mx(a,b,c);
            mx = max(l->mx, r->mx);
        }

    }
    void upd_mn(int a,int b,int c){
        prop();
        if (a <= s && e <= b){
            mn = min(mn, c);
            lazy_mn = min(lazy_mn, c);
        }else if (a > e || s > b) return;
        else{
            l->upd_mn(a,b,c); r->upd_mn(a,b,c);
            mn = min(l->mn, r->mn);
        }
    }

    pi qry(int a,int b){
        prop();
        if (a <= s && e <= b) return pi(mn, mx);
        else if (a > e || s > b) return pi(INF, -INF);
        else{
            pi x = l->qry(a,b), y = r->qry(a,b);
            return pi(min(x.f,y.f), max(x.s,y.s));
        }
    }
}*root[21];

int N,K,M,Q,A[maxn],B[maxn],S[maxn],T[maxn];
pi dp[maxn][21];
int32_t main(){
    fast;
    cin >> N >> K >> M;
    FOR(i,1,M) cin >> A[i] >> B[i];
    cin >> Q;
    FOR(i,1,Q) cin >> S[i] >> T[i];

    FOR(i,0,20) root[i] = new node(1,N);
    FOR(i,1,M){
        if (A[i] < B[i]) root[0]->upd_mx(A[i],min(A[i] + K - 1, B[i]), B[i]);
        else root[0]->upd_mn(max(B[i], A[i] - K + 1), A[i], B[i]);
    }
    FOR(i,1,N) dp[i][0] = root[0]->qry(i,i);
    FOR(k,1,20){
        FOR(i,1,N) dp[i][k] = root[k-1]->qry(dp[i][k-1].f, dp[i][k-1].s);
        FOR(i,1,N) root[k]->upd_mn(i,i,dp[i][k].f), root[k]->upd_mx(i,i,dp[i][k].s);
    }
    if (DEBUG) FOR(i,1,N) cout << dp[i][0].f << ' ' << dp[i][0].s << '\n';

    FOR(i,1,Q){
        pi cur = pi(S[i],S[i]);
        int ans = 0;
        if (DEBUG) cout << "QUERY " << i << '\n';
        DEC(k,20,0) {
            if (DEBUG) cout << cur.f << ' ' << cur.s << '\n';
            pi x = root[k]->qry(cur.f,cur.s);
            
            if (!(x.f <= T[i] && T[i] <= x.s)){
                ans += (1<<k);
                cur = x;
            }
        }
        pi x = root[0]->qry(cur.f,cur.s);
        if (x.f <= T[i] && T[i] <= x.s) cout << ans+1 << '\n';
        else cout << -1 << '\n';
    }

   
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 7 ms 1472 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1352 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 5 ms 1364 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 6 ms 1464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 7 ms 1472 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1352 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 5 ms 1364 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 6 ms 1464 KB Output is correct
13 Correct 56 ms 7672 KB Output is correct
14 Correct 53 ms 7668 KB Output is correct
15 Correct 38 ms 7508 KB Output is correct
16 Correct 54 ms 7676 KB Output is correct
17 Correct 56 ms 7608 KB Output is correct
18 Correct 41 ms 7668 KB Output is correct
19 Correct 49 ms 7316 KB Output is correct
20 Correct 41 ms 7636 KB Output is correct
21 Correct 29 ms 7636 KB Output is correct
22 Correct 52 ms 7676 KB Output is correct
23 Correct 54 ms 7672 KB Output is correct
24 Correct 57 ms 7668 KB Output is correct

Subtask #3
0 / 11.0

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

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

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

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1368 KB Output is correct
2 Correct 7 ms 1472 KB Output is correct
3 Correct 4 ms 1364 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1352 KB Output is correct
6 Correct 5 ms 1364 KB Output is correct
7 Correct 6 ms 1364 KB Output is correct
8 Correct 5 ms 1364 KB Output is correct
9 Correct 6 ms 1364 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 6 ms 1364 KB Output is correct
12 Correct 6 ms 1464 KB Output is correct
13 Correct 56 ms 7672 KB Output is correct
14 Correct 53 ms 7668 KB Output is correct
15 Correct 38 ms 7508 KB Output is correct
16 Correct 54 ms 7676 KB Output is correct
17 Correct 56 ms 7608 KB Output is correct
18 Correct 41 ms 7668 KB Output is correct
19 Correct 49 ms 7316 KB Output is correct
20 Correct 41 ms 7636 KB Output is correct
21 Correct 29 ms 7636 KB Output is correct
22 Correct 52 ms 7676 KB Output is correct
23 Correct 54 ms 7672 KB Output is correct
24 Correct 57 ms 7668 KB Output is correct
25 Execution timed out 2094 ms 364100 KB Time limit exceeded
26 Halted 0 ms 0 KB -