oj.uz

Submission #536057

# Submission time Handle Problem Language Result Execution time Memory
536057 2022-03-12T08:40:29 Z zaneyu Railway Trip 2 (JOI22_ho_t4) C++14
11 / 100
 1129 ms 61372 KB 
/*input
12 1
5
1 7
10 12
3 5
8 10
5 9
7
2 11
5 8
3 12
4 6
1 9
9 10
1 4
*/
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FILL(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const int INF=0x3f3f3f3f;
const ll MOD=1e9+7;
const ld PI=acos(-1);
const ld eps=1e-6;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
ll sub(ll a,ll b){
    ll x=a-b;
    while(x<0) x+=MOD;
    while(x>MOD) x-=MOD;
    return x;
}
ll mult(ll a,ll b){
    return (a*b)%MOD;
}
ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=(res*a)%MOD;
        a=(a*a)%MOD;
        b>>=1;
    }
    return res;
}
template<typename T1,typename T2>
ostream& operator<<(ostream& out,pair<T1,T2> P){
    out<<P.f<<' '<<P.s;
    return out;
}
template<typename T>
ostream& operator<<(ostream& out,vector<T> V){
    REP(i,sz(V)) out<<(V[i])<<((i!=sz(V)-1)?" ":"\n");
    return out;
}
const ll maxn=1e5+5;
const ll maxlg=__lg(maxn)+2; 
pii table[maxn][17];
int L[maxn],R[maxn];
pii arr[maxn];
struct seg{
    int mx[4*maxn],mn[4*maxn];
    void build(int idx,int l,int r){
        if(l==r){
            mn[idx]=arr[l].f,mx[idx]=arr[l].s;
            return;
        }
        int mid=(l+r)/2;
        build(idx*2,l,mid),build(idx*2+1,mid+1,r);
        mx[idx]=max(mx[idx*2],mx[idx*2+1]);
        mn[idx]=min(mn[idx*2],mn[idx*2+1]);
    }
    int qmn(int idx,int l,int r,int ql,int qr){
        if(l>qr or r<ql) return INF;
        if(ql<=l and r<=qr) return mn[idx];
        int mid=(l+r)/2;
        return min(qmn(idx*2,l,mid,ql,qr),qmn(idx*2+1,mid+1,r,ql,qr));
    }
    int qmx(int idx,int l,int r,int ql,int qr){
        if(l>qr or r<ql) return 0;
        if(ql<=l and r<=qr) return mx[idx];
        int mid=(l+r)/2;
        return max(qmx(idx*2,l,mid,ql,qr),qmx(idx*2+1,mid+1,r,ql,qr));
    }
}seg[20];
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int n,k,m,q;
    cin>>n>>k>>m;
    vector<pii> l,r;
    REP(i,m){
        int a,b;
        cin>>a>>b;
        --a,--b;
        if(a<b) r.pb({a,b});
        else l.pb({a,b});
    }
    sort(ALL(r));
    int p=0,p2=0;
    multiset<int> s;
    REP(i,n){
        while(p2<sz(r) and r[p2].f<=i) s.insert(r[p2++].s);
        while(p<sz(r) and r[p].f+k<=i) s.erase(s.find(r[p++].s));
        if(!sz(s)) R[i]=i;
        else R[i]=*prev(s.end());
    }
    s.clear();
    sort(ALL(l));
    reverse(ALL(l));
    p=p2=0;
    for(int i=n-1;i>=0;i--){
        while(p2<sz(l) and l[p2].f>=i) s.insert(l[p2++].s);
        while(p<sz(l) and l[p].f-k>=i) s.erase(s.find(l[p++].s));
        if(!sz(s)) L[i]=i;
        else L[i]=*s.begin();
    }
    REP(i,n) table[i][0]={L[i],R[i]},assert(L[i]<=R[i]);
    REP1(j,16){
        REP(i,n){
            arr[i]=table[i][j-1];
        }
        seg[j-1].build(1,0,n-1);
        REP(i,n){
            table[i][j]={seg[j-1].qmn(1,0,n-1,table[i][j-1].f,table[i][j-1].s),seg[j-1].qmx(1,0,n-1,table[i][j-1].f,table[i][j-1].s)};
            //cout<<table[i][j]<<'\n';
        }
    }
    int j=16;
    REP(i,n){
        arr[i]=table[i][j];
    }
    seg[j].build(1,0,n-1);
    cin>>q;
    while(q--){
        int a,b;
        cin>>a>>b;
        --a,--b;
        pii z={a,a};
        int ans=1;
        for(int j=16;j>=0;j--){
            pii nw={seg[j].qmn(1,0,n-1,z.f,z.s),seg[j].qmx(1,0,n-1,z.f,z.s)};
            if(!(nw.f<=b and b<=nw.s)) ans+=(1<<j),z=nw;
        }
        if(ans==(1<<17)) ans=-1;
        cout<<ans<<'\n';
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Runtime error 2 ms 596 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Runtime error 2 ms 596 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 581 ms 51088 KB Output is correct
2 Correct 555 ms 51256 KB Output is correct
3 Correct 605 ms 51188 KB Output is correct
4 Correct 541 ms 51020 KB Output is correct
5 Correct 223 ms 54088 KB Output is correct
6 Correct 563 ms 51964 KB Output is correct
7 Correct 148 ms 56424 KB Output is correct
8 Correct 113 ms 52512 KB Output is correct
9 Correct 102 ms 53356 KB Output is correct
10 Correct 449 ms 51920 KB Output is correct
11 Correct 442 ms 56444 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 47 ms 23616 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 769 ms 55268 KB Output is correct
2 Correct 1118 ms 51444 KB Output is correct
3 Correct 1129 ms 51012 KB Output is correct
4 Correct 1045 ms 50968 KB Output is correct
5 Correct 780 ms 50484 KB Output is correct
6 Correct 828 ms 50380 KB Output is correct
7 Correct 498 ms 55712 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 11 ms 1528 KB Output is correct
10 Correct 418 ms 55688 KB Output is correct
11 Correct 577 ms 61372 KB Output is correct
12 Correct 584 ms 54936 KB Output is correct
13 Correct 643 ms 59900 KB Output is correct
14 Correct 2 ms 724 KB Output is correct
15 Runtime error 3 ms 596 KB Execution killed with signal 6
16 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Runtime error 2 ms 596 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -