oj.uz

Submission #703383

# Submission time Handle Problem Language Result Execution time Memory
703383 2023-02-27T08:13:37 Z Aestivate Railway Trip 2 (JOI22_ho_t4) C++17
27 / 100
 2000 ms 13644 KB 
#include<bits/stdc++.h>
#include<random>

using namespace std;

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

#define ss(n) fixed<<setprecision(n)
#define ll long long
#define int ll
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define ld long double
#define pb push_back
#define pii pair<int,int>
#define rep(i,a) for(int i=1;i<=a;i++)
#define rep0(i,a) for(int i=0;i<a;i++)
#define F first
#define S second
#define float double

ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}

const ld pi=3.14159265358979323846264338327950288419716939931;
const int lar=3e18;
const int mol1=1e9+7;
const int mol2=998224353;
const int mol3=1e15+9;
const int bb=137;

int mxl[400005],mxr[400005],lal1[400005]={0},lal2[400005];

void build(int l,int r,int ind){
    if(l==r){
        mxl[ind]=l;mxr[ind]=l;
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ind*2);build(mid+1,r,ind*2+1);
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}

void upd1(int l,int r ,int l1,int r1,int vv,int ind){
    if(l1<=l&&r<=r1) {
        lal1[ind]=min(lal1[ind],vv);
        mxl[ind]=min(mxl[ind],vv);
        return;
    }
    int mid=l+r>>1;
    if(lal1[ind]!=lar){
        int p=lal1[ind];lal1[ind]=lar;
        lal1[ind*2]=min(lal1[ind*2],p);
        lal1[ind*2+1]=min(lal1[ind*2+1],p);mxl[ind*2]=min(mxl[ind*2],p);
        mxl[ind*2+1]=min(mxl[ind*2+1],p);
    }
    if(r1<=mid) upd1(l,mid,l1,r1,vv,ind*2);
    else if(l1>mid) upd1(mid+1,r,l1,r1,vv,ind*2+1);
    else{
        upd1(l,mid,l1,r1,vv,ind*2);upd1(mid+1,r,l1,r1,vv,ind*2+1);
    }
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
}

void upd2(int l,int r ,int l1,int r1,int vv,int ind){
    if(l1<=l&&r<=r1) {
        lal2[ind]=max(lal2[ind],vv);
        mxr[ind]=max(mxr[ind],vv);
        return;
    }
    int mid=l+r>>1;
    if(lal2[ind]!=-lar){
        int p=lal2[ind];lal2[ind]=-lar;
        lal2[ind*2]=max(lal2[ind*2],p);
        lal2[ind*2+1]=max(lal2[ind*2+1],p);mxr[ind*2]=max(mxr[ind*2],p);
        mxr[ind*2+1]=max(mxr[ind*2+1],p);
    }
    if(r1<=mid) upd2(l,mid,l1,r1,vv,ind*2);
    else if(l1>mid) upd2(mid+1,r,l1,r1,vv,ind*2+1);
    else{
        upd2(l,mid,l1,r1,vv,ind*2);upd2(mid+1,r,l1,r1,vv,ind*2+1);
    }
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}

int val1(int l,int r,int l1,int r1,int ind){
    if(l1<=l&&r<=r1) return mxl[ind];
    int mid=l+r>>1;
    if(lal1[ind]!=lar){
        int p=lal1[ind];lal1[ind]=lar;
        lal1[ind*2]=min(lal1[ind*2],p);
        lal1[ind*2+1]=min(lal1[ind*2+1],p);mxl[ind*2]=min(mxl[ind*2],p);
        mxl[ind*2+1]=min(mxl[ind*2+1],p);
    }
    if(r1<=mid) return val1(l,mid,l1,r1,ind*2);
    else if(l1>mid) return val1(mid+1,r,l1,r1,ind*2+1);
    else return  min(val1(l,mid,l1,r1,ind*2),val1(mid+1,r,l1,r1,ind*2+1));
    mxl[ind]=min(mxl[ind*2],mxl[ind*2+1]);
}

int val2(int l,int r,int l1,int r1,int ind){
    if(l1<=l&&r<=r1) return mxr[ind];
    int mid=l+r>>1;
    if(lal2[ind]!=-lar){
        int p=lal2[ind];lal2[ind]=-lar;
        lal2[ind*2]=max(lal2[ind*2],p);
        lal2[ind*2+1]=max(lal2[ind*2+1],p);mxr[ind*2]=max(mxr[ind*2],p);
        mxr[ind*2+1]=max(mxr[ind*2+1],p);
    }
    if(r1<=mid) return val2(l,mid,l1,r1,ind*2);
    else if(l1>mid) return val2(mid+1,r,l1,r1,ind*2+1);
    else return  max(val2(l,mid,l1,r1,ind*2),val2(mid+1,r,l1,r1,ind*2+1));
    mxr[ind]=max(mxr[ind*2],mxr[ind*2+1]);
}



void solve()
{
    int n,k;
    cin>>n>>k;
    rep(i,4*n){
        lal1[i]=lar,lal2[i]=-lar;
    }
    build(1,n,1);
    int m;
    cin>>m;
    rep(i,m){
        int g,h;
        cin>>g>>h;
        if(g<=h){
            upd2(1,n,g,min(g+k-1,h),h,1);
        }
        else{
            upd1(1,n,max(g-k+1,h),g,h,1);
        }
    }
    int q;
    cin>>q;
    rep(i,q){
        int g,h;
        cin>>g>>h;
        int l=g,r=g;
        int tt=0;
        while(h<l||h>r){
            tt++;
            int g1=l,g2=r;
            l=val1(1,n,g1,g2,1);
            r=val2(1,n,g1,g2,1);
            if(l==g1&&r==g2) break;
        }
        if(h<l||h>r) cout<<-1<<"\n";
        else cout<<tt<<"\n";
    }
}

signed main()
{
    IO
    solve();
    return 0;
}

Compilation message

Main.cpp: In function 'void build(long long int, long long int, long long int)':
Main.cpp:39:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void upd1(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:51:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'void upd2(long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int val1(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:89:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |     int mid=l+r>>1;
      |             ~^~
Main.cpp: In function 'long long int val2(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:104:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  104 |     int mid=l+r>>1;
      |             ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 308 ms 556 KB Output is correct
14 Correct 166 ms 552 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 75 ms 568 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 524 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 2 ms 572 KB Output is correct
23 Correct 5 ms 468 KB Output is correct
24 Correct 6 ms 576 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 11576 KB Output is correct
2 Correct 42 ms 11592 KB Output is correct
3 Correct 53 ms 11724 KB Output is correct
4 Correct 34 ms 11444 KB Output is correct
5 Correct 130 ms 13004 KB Output is correct
6 Correct 87 ms 12976 KB Output is correct
7 Correct 94 ms 12600 KB Output is correct
8 Correct 68 ms 11776 KB Output is correct
9 Correct 81 ms 11856 KB Output is correct
10 Correct 112 ms 12972 KB Output is correct
11 Correct 91 ms 12972 KB Output is correct

Subtask #4
0 / 25.0

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

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 13644 KB Output is correct
2 Execution timed out 2087 ms 11960 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 308 ms 556 KB Output is correct
14 Correct 166 ms 552 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 2 ms 468 KB Output is correct
17 Correct 75 ms 568 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 524 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 2 ms 572 KB Output is correct
23 Correct 5 ms 468 KB Output is correct
24 Correct 6 ms 576 KB Output is correct
25 Correct 42 ms 11576 KB Output is correct
26 Correct 42 ms 11592 KB Output is correct
27 Correct 53 ms 11724 KB Output is correct
28 Correct 34 ms 11444 KB Output is correct
29 Correct 130 ms 13004 KB Output is correct
30 Correct 87 ms 12976 KB Output is correct
31 Correct 94 ms 12600 KB Output is correct
32 Correct 68 ms 11776 KB Output is correct
33 Correct 81 ms 11856 KB Output is correct
34 Correct 112 ms 12972 KB Output is correct
35 Correct 91 ms 12972 KB Output is correct
36 Execution timed out 2060 ms 11816 KB Time limit exceeded
37 Halted 0 ms 0 KB -