Submission #685396

#	Time	Username	Problem	Language	Result	Execution time	Memory
685396		browntoad	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	901 ms	462496 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
// #define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif

const ll inf = 1ll<<60;
const int iinf=100002;
const ll mod = 1e9+7;
const ll maxn=1e5+5;
const double PI=acos(-1);

ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}

ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}

//=======================================================================================

pii def = {iinf, 0};
const int mxpw=17;
pii sparsel[mxpw][maxn][mxpw], sparser[mxpw][maxn][mxpw];
int smol[maxn];
int pw2[maxn];
vector<pii> seg(4*maxn);
vector<pii> tag(4*maxn);
void push(int x, int l, int r){
	seg[x].f=min(seg[x].f, tag[x].f);
	seg[x].s=max(seg[x].s, tag[x].s);
	if (l!=r){
		tag[x+x].f=min(tag[x].f, tag[x+x].f);
		tag[x+x].s=max(tag[x].s, tag[x+x].s);
		tag[x+x+1].f=min(tag[x].f, tag[x+x+1].f);
		tag[x+x+1].s=max(tag[x].s, tag[x+x+1].s);
	}
	tag[x]=def;
}
void pull(int x){
	seg[x].f=min(seg[x+x].f, seg[x+x+1].f);
	seg[x].s=max(seg[x+x].s, seg[x+x+1].s);
}
void build(int l, int r, int x){
	if (l==r){
		seg[x] = {l, l};
		return;
	}
	int mid = (l+r) >> 1;
	build(l, mid, x+x);
	build(mid+1, r, x+x+1);
	pull(x);
}
void modify(int l, int r, int nl, int nr, int x, pii val){
	if (l>nr||r<nl){
		push(x, nl, nr);
		return;
	}
	if (l<=nl&&nr<=r){
		tag[x].f=min(tag[x].f, val.f);
		tag[x].s=max(tag[x].s, val.s);
		push(x, nl, nr);
		return;
	}
	push(x, nl, nr);
	int mid = (nl+nr) >> 1;
	modify(l, r, nl, mid, x+x, val);
	modify(l, r, mid+1, nr, x+x+1, val);
	pull(x);
}
pii query(int l, int r, int pos, int x){
	if (l==r){
		push(x, l, r);
		return seg[x];
	}
	push(x, l, r);
	int mid = (l+r) >> 1;
	if (l<=pos && pos<=mid){
		return query(l, mid, pos, x+x);
	}
	else {
		return query(mid+1, r, pos, x+x+1);
	}
}

int n, k;
int m, q;
void init(){
	REP(i, 4*maxn){
		tag[i] = def;
	}
	build(1, n, 1);
	pw2[0]=1;
	REP1(i, 18){
		pw2[i]=pw2[i-1]*2;
	}
    REP1(i, n+2){
    	smol[i]=log2(i);
    }
    REP(i, mxpw){
    	REP1(j, n){
    		REP(k, mxpw){
    			sparsel[i][j][k]=sparser[i][j][k]={j, j};
    		}
    	}
    }
}
pii eq(int l, int r){
	int tl, tr;
	if (l<r){
		tl=l;
		tr=l+k-1;
		if (tr>r) tr=r;
	}
	else {
		tl=l;
		tr=l-k+1;
		if (tr<r){
			tr=r;
		}
		swap(tl, tr);
	}
	return {tl, tr};
}
pii rangval(int a, pii cur){
	int cd=cur.s-cur.f+1;
	pii ret;
	ret.s = max(sparsel[a][cur.f][smol[cd]].s, sparser[a][cur.s][smol[cd]].s);
	ret.f = min(sparsel[a][cur.f][smol[cd]].f, sparser[a][cur.s][smol[cd]].f);
	return ret;
}
void makesparse(){
	REP1(i, n){
		sparsel[0][i][0] = query(1, n, i, 1);
		sparser[0][i][0] = sparsel[0][i][0];
		// cout<<sparsel[0][i][0].f<<' '<<sparsel[0][i][0].s<<endl;
	}
	int tl, tr;
	pii ret;
	REP(t, mxpw){
		if (t!=0){
			REP1(i, n){
				tl=sparsel[t-1][i][0].f; tr=sparsel[t-1][i][0].s;
				ret = rangval(t-1, {tl, tr});
				sparsel[t][i][0] = sparser[t][i][0] = ret;
			}
		}
		for (int i=n; i>=1; i--){
			REP1(j, mxpw-1){
				sparsel[t][i][j].s = max(sparsel[t][i][j-1].s, sparsel[t][min(i+pw2[j-1], n)][j-1].s);
				sparsel[t][i][j].f = min(sparsel[t][i][j-1].f, sparsel[t][min(i+pw2[j-1], n)][j-1].f);
			}
		}
		for (int i=1; i<=n; i++){
			REP1(j, mxpw-1){
				sparser[t][i][j].s = max(sparser[t][i][j-1].s, sparser[t][max(i-pw2[j-1], 1)][j-1].s);
				sparser[t][i][j].f = min(sparser[t][i][j-1].f, sparser[t][max(i-pw2[j-1], 1)][j-1].f);
			}
		}
	}
	

}

void runq(){
	pii cur, ret;
	REP(i, q){
		int l, r; cin>>l>>r;
		int res = 0;
		if (l<r){
			cur = {l, l};
			RREP(j, mxpw){
				ret = rangval(j, cur);
				if (ret.s >= r) continue;
				res += pw2[j];
				cur = ret;
			}
			if (res == (1<<mxpw)-1){
				res = -1;
			}
			else res++;
		}
		else {
			cur = {l, l};
			RREP(j, mxpw){
				ret = rangval(j, cur);
				if (ret.f <= r) continue;
				res += pw2[j];
				cur = ret;
				// cout<<i<<' '<<j<<' '<<cur.f<<' '<<cur.s<<endl;
			}
			if (res == (1<<mxpw)-1){
				res = -1;
			}
			else res++;
		}
		cout<<res<<endl;
	}
}
signed main (){
    IOS();
    cin>>n>>k;
    cin>>m;
    init();
    REP(i, m){
    	int l, r; cin>>l>>r;
    	pii ret = eq(l, r);
    	// cout<<ret.f<<' '<<ret.s<<endl;
    	if (l<r){
    		modify(ret.f, ret.s, 1, n, 1, {iinf, r});
    	}
    	else { // r to l
    		modify(ret.f, ret.s, 1, n, 1, {r, 0});
    	}
    }
    makesparse();
    cin>>q;
    runq();
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13