oj.uz

Submission #534825

# Submission time Handle Problem Language Result Execution time Memory
534825 2022-03-09T03:16:49 Z PixelCat Railway Trip 2 (JOI22_ho_t4) C++14
35 / 100
 963 ms 322996 KB 
/*       code by the cute PixelCat owo       */
/*   as cute as nacho neko (aka. my wife)!   */
// #pragma GCC
// optimize("O4,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
using uLL = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second
#define L(id) (id * 2 + 1)
#define R(id) (id * 2 + 2)
#define LO(x) (x & (-x))

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

// #define MOD (int)(998244353)
#define MOD (int)((LL)1e9 + 7)
#define INF (int)(9000000000000000000ll)  // 9e18
#define EPS (1e-6)

#ifdef NYAOWO
#include "library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod) {
    int ans = 1;
    while (p) {
        if (p & 1) ans = ans * b % mod;
        p /= 2;
        b = b * b % mod;
    }
    return ans;
}
int fpow(int b, int p) {
    return fpow(b, p, MOD);
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_b > _a) _a = _b;
}
// mt19937_64 rng(
//     chrono::steady_clock::now().time_since_epoch().count());

int n;

struct Sparse{
    int a[100010][20];
    void set(int i,int x){
        a[i][0]=x;
    }
    void build(){
        For(j,0,18) For(i,1,n){
            int i2=i+(1<<j);
            if(i2>n) a[i][j+1]=a[i][j];
            else a[i][j+1]=max(a[i][j],a[i2][j]);
        }
    }
    int rmq(int l,int r){
        int k=__lg(r-l+1);
        return max(a[l][k],a[r-(1<<k)+1][k]);
    }
}sp[20];

// take n trains from s
int step(int s,int ns){
    int r=s;
    For(j,0,19) if(ns&(1<<j)){
        r=sp[j].rmq(s,r);
    }
    return r;
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    // miku sama bless me >/////<
    cin>>n;
    int k; cin>>k;
    int m; cin>>m;
    {
        vector<pii> v(m);
        for(auto &i:v) cin>>i.F>>i.S;
        sort(all(v));
        // debug(v);
        multiset<int> st;
        int itl=0,itr=-1;
        For(r,1,n){
            while(itr<m-1 && v[itr+1].F==r){
                itr++;
                st.insert(v[itr].S);
            }
            while(itl<=m-1 && v[itl].F<=r-k){
                st.erase(st.find(v[itl].S));
                itl++;
            }
            int res=r;
            if(sz(st)) res=max(res,*st.rbegin());
            sp[0].set(r,res);
        }
    }
    debug("owo");
    sp[0].build();
    For(j,1,19){
        For(i,1,n){
            sp[j].set(i,sp[j-1].rmq(i,sp[j-1].a[i][0]));
        }
        sp[j].build();
    }
    int q; cin>>q;
    while(q--){
        int s,t; cin>>s>>t;
        int lo=-1,hi=(1<<20)-1;
        while(hi-lo>1){
            int mi=(hi+lo)/2;
            if(step(s,mi)>=t) hi=mi;
            else lo=mi;
        }
        if(hi+1==(1<<20)){
            cout<<"-1\n";
        }else{
            cout<<hi<<"\n";
        }
    }
    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 537 ms 313400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 736 ms 317240 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 963 ms 316824 KB Output is correct
2 Correct 944 ms 313636 KB Output is correct
3 Correct 898 ms 313720 KB Output is correct
4 Correct 814 ms 313696 KB Output is correct
5 Correct 678 ms 313668 KB Output is correct
6 Correct 651 ms 313548 KB Output is correct
7 Correct 615 ms 318200 KB Output is correct
8 Correct 2 ms 1356 KB Output is correct
9 Correct 10 ms 6860 KB Output is correct
10 Correct 698 ms 317192 KB Output is correct
11 Correct 795 ms 322864 KB Output is correct
12 Correct 762 ms 313680 KB Output is correct
13 Correct 825 ms 321464 KB Output is correct
14 Correct 2 ms 1356 KB Output is correct
15 Correct 9 ms 6768 KB Output is correct
16 Correct 528 ms 313356 KB Output is correct
17 Correct 829 ms 322996 KB Output is correct
18 Correct 871 ms 313672 KB Output is correct
19 Correct 724 ms 313644 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1356 KB Output isn't correct
2 Halted 0 ms 0 KB -