Submission #794691

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
794691	2023-07-26T19:07:48 Z	Antekb	Railway Trip (JOI17_railway_trip)	C++17	100 / 100	1010 ms	44524 KB

railway_trip

#include<bits/stdc++.h>

#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")
 
#define st first
#define nd second
#define pb push_back
#define eb emplace_back
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)
 
using namespace std;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~~
 
template <typename H, typename T> 
ostream& operator<<(ostream& os, pair<H, T> m){
	return os <<"("<< m.st<<", "<<m.nd<<")";
}
template <typename H> 
ostream& operator<<(ostream& os, vector<H> V){
	os<<"{";
	for(int i=0; i<V.size(); i++){
		if(i)os<<" ";
		os<<V[i];
	}
	os<<"}";
	return os;
}
 
void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);
//#define deb(x...) ;
 
///~~~~~~~~~~~~~~~~~~~~~~~~~
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

 
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
 
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int K=17, N=1<<K, INF=1e9+5, mod2=1e9+7, mod=998244353;

struct modint{
	int n=0;
	modint(){}
	modint(ll x){
		n=x%mod;
		if(n<0)n+=mod;
	}
	operator int(){
		return n;
	}
	modint operator+(modint a){a.n = n+a.n; if(a.n>=mod)a.n-=mod;return a;}
	modint operator+=(modint a){return (*this)=(*this)+a;}
	modint operator-(modint a){a.n = n-a.n; if(a.n<0)a.n+=mod;return a;}
	modint operator-=(modint a){return (*this)=(*this)-a;}
	modint operator*(modint a){a.n = (n*1ll*a.n)%mod; return a;}
	modint operator*=(modint a){return (*this)=(*this)*a;}
	modint operator^(const ll &m)const{
		modint a(1);
		if(m==0)return a;
		if(m==1)return (*this);
		a=(*this)^(m/2);
		a*=a;
		return a*((*this)^(m&1));
	}
	modint odw(){
		return (*this)^((ll)mod-2);
	}
	modint operator/(modint a){return (*this)*a.odw();}
	modint operator/=(modint a){return (*this)=(*this)/a;}
	bool operator==(modint a){return a.n==n;}
	friend ostream& operator<<(ostream& os, modint m) {
		return os << m.n; 
	}
};
/*modint fact[N], fact2[N];
typedef vector<modint> vm;
void factinit(){
    fact[0]=1;
    for(int i=1; i<N; i++){
        fact[i]=(fact[i-1]*modint(i))%mod;
    }
    fact2[N-1]=fact[N-1].odw();
    for(int i=N-2; i>=0; i--){
    	fact2[i]=(fact2[i+1]*modint(i+1))%mod;
    }
}
modint npok(int _n, int _k){
 	if(_n<_k)return 0;
    return fact[_n]*fact2[_k]*fact2[_n-_k];
}*/
int los(int a, int b){
	return a+(rng())%(b-a+1);
}
vector<int> typ[N+N], tab[N+N];//permutcja, stale
int maks[N+N];
vector<int> gdzie[N];
int get(int l, int r){
	int a=0;
	for(l+=N, r+=N; l<r; l>>=1, r>>=1){
		if(l&1)a=max(a, maks[l++]);
		if(r&1)a=max(a, maks[--r]);
	}
	return a;
}
pair<vi, vi> zloz(vi &A, vi& c1, vi &B, vi& c2){ //A(B(i)) - B glebiej
	vi C(3), c3(3);
	for(int i=0; i<3; i++){
		C[i]=A[B[i]];
		c3[i]=c2[i]+c1[B[i]];
	}
	return mp(C, c3);
}
void prop(int v){
	if(v>=N)return;
	int l=v+v, r=l+1;
	auto a=zloz(typ[v], tab[v], typ[l], tab[l]);
	typ[l]=a.st;
	tab[l]=a.nd;
	a=zloz(typ[v], tab[v], typ[r], tab[r]);
	typ[r]=a.st;
	tab[r]=a.nd;
	typ[v]={0, 1, 2};
	tab[v]={0, 0, 0};
}
void update(int v, int L, int R, int l, int r, vi &A, vi &c){
	if(L==l && r==R){
		auto a=zloz(A, c, typ[v], tab[v]);
		typ[v]=a.st;
		tab[v]=a.nd;
		return;
	}
	int M=(L+R)>>1;
	prop(v);
	if(l<=M)update(v+v, L, M, l, min(M, r), A, c);
	if(r>M)update(v+v+1, M+1, R, max(M+1, l), r, A, c);
}
void upd(int l, int r, int a, int b){
	if(l>r)return;
	vi A(3);
	vi c(3);
	for(int i=0; i<3; i++){
		int L=a, R=b+i-1;
		if(L>R+1)L=R+1;
		if(L+1<R)R=L+1;
		c[i]=L;
		A[i]=R-L+1;
	}
	update(1, 0, N-1, l, r, A, c);
}
pii val(int v){
	int c=0, t=1;
	v+=N;
	for(;v>0; v>>=1){
		c+=tab[v][t];
		t=typ[v][t];
	}
	return mp(c, c+t-1);
}
int main(){
	//factinit();
	//BOOST
	int n, k, q;
	cin>>n>>k>>q;
	set<int> S;
	for(int i=0; i<n; i++){
		S.insert(i);
		cin>>maks[N+i];
		gdzie[maks[N+i]].pb(i);
	}
	for(int i=N-1; i>0; i--){
		maks[i]=max(maks[i+i], maks[i+i+1]);
	}
	for(int i=0; i<N+N; i++){
		typ[i]={0, 1, 2};
		tab[i]={0, 0, 0};
	}
	vector<pair<pii, pii>> Q;
	for(int i=0; i<q; i++){
		int a, b;
		cin>>a>>b;
		a--;
		b--;
		if(a>b)swap(a, b);
		int m=get(a, b+1);
		//deb(a, b, m);
		Q.eb(mp(m, i), mp(a, b));
	}
	sor(Q);
	int wskq=0, wskq2=0;
	vi ans(q);
	for(int i=1; i<=k; i++){
		//deb(i);
		while(wskq<q && Q[wskq].st.st==i){
			int a=Q[wskq].nd.st, b=Q[wskq].nd.nd;
			ans[Q[wskq].st.nd]=val(a).nd+val(b).st+upper_bound(all(gdzie[i]), b)-lower_bound(all(gdzie[i]), a)-1;
			//deb(Q[wskq]);
			wskq++;
		}
		if(i<k){
			vector<int> co;
			for(int j=0; j<gdzie[i].size(); j++){
				co.pb(gdzie[i][j]);
				S.erase(gdzie[i][j]);
				if(j==gdzie[i].size()-1 || *S.lower_bound(gdzie[i][j])!=gdzie[i][j+1]){
					int L=*(--S.lower_bound(gdzie[i][j]));
					int R=*(S.lower_bound(gdzie[i][j]));
					upd(L+1, co[0]-1, 0, co.size());
					for(int l=0; l<co.size()-1; l++){
						upd(co[l]+1, co[l+1]-1, l+1, co.size()-l-1);
					}
					upd(co.back()+1, R-1, co.size(), 0);
					for(int l=0; l<co.size(); l++){
						upd(co[l], co[l], l+1, co.size()-l);
					}
					co.clear();
				}
			}
			while(wskq2<q && Q[wskq2].st.st==i){
				int a=Q[wskq2].nd.st, b=Q[wskq2].nd.nd;
				ans[Q[wskq2].st.nd]=min(ans[Q[wskq2].st.nd], val(a).st+val(b).nd+1);
				wskq2++;
			}
		}
		/*for(int j=0; j<n; j++){
			if(maks[j+N]<=i){
				deb(val(j));
			}
		}*/
	}
	for(int i=0; i<q; i++){
		cout<<ans[i]-1<<"\n";
	}
}

Subtask #1

5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	31 ms	32588 KB	Output is correct
2	Correct	30 ms	32588 KB	Output is correct
3	Correct	30 ms	32588 KB	Output is correct
4	Correct	30 ms	32612 KB	Output is correct
5	Correct	30 ms	32556 KB	Output is correct
6	Correct	31 ms	32604 KB	Output is correct
7	Correct	30 ms	32596 KB	Output is correct
8	Correct	30 ms	32548 KB	Output is correct
9	Correct	30 ms	32548 KB	Output is correct

Subtask #2

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	32648 KB	Output is correct
2	Correct	522 ms	38380 KB	Output is correct
3	Correct	614 ms	38464 KB	Output is correct
4	Correct	684 ms	38336 KB	Output is correct
5	Correct	694 ms	38476 KB	Output is correct
6	Correct	766 ms	38604 KB	Output is correct
7	Correct	774 ms	40260 KB	Output is correct
8	Correct	328 ms	38464 KB	Output is correct
9	Correct	541 ms	39324 KB	Output is correct
10	Correct	463 ms	38856 KB	Output is correct
11	Correct	542 ms	39436 KB	Output is correct
12	Correct	541 ms	39216 KB	Output is correct
13	Correct	530 ms	38988 KB	Output is correct
14	Correct	556 ms	39444 KB	Output is correct
15	Correct	551 ms	39116 KB	Output is correct
16	Correct	536 ms	39040 KB	Output is correct
17	Correct	682 ms	38844 KB	Output is correct
18	Correct	683 ms	38752 KB	Output is correct
19	Correct	706 ms	41116 KB	Output is correct

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	732 ms	41964 KB	Output is correct
2	Correct	671 ms	41876 KB	Output is correct
3	Correct	730 ms	41932 KB	Output is correct
4	Correct	737 ms	42068 KB	Output is correct
5	Correct	743 ms	41928 KB	Output is correct
6	Correct	763 ms	42044 KB	Output is correct
7	Correct	775 ms	41968 KB	Output is correct
8	Correct	360 ms	41928 KB	Output is correct
9	Correct	565 ms	41928 KB	Output is correct
10	Correct	581 ms	42044 KB	Output is correct
11	Correct	586 ms	41916 KB	Output is correct
12	Correct	584 ms	41924 KB	Output is correct
13	Correct	578 ms	42028 KB	Output is correct
14	Correct	524 ms	41932 KB	Output is correct
15	Correct	482 ms	41816 KB	Output is correct
16	Correct	564 ms	41792 KB	Output is correct

Subtask #4

55.0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	922 ms	43628 KB	Output is correct
2	Correct	949 ms	43736 KB	Output is correct
3	Correct	942 ms	42256 KB	Output is correct
4	Correct	944 ms	42676 KB	Output is correct
5	Correct	570 ms	41920 KB	Output is correct
6	Correct	656 ms	42944 KB	Output is correct
7	Correct	692 ms	42964 KB	Output is correct
8	Correct	595 ms	42560 KB	Output is correct
9	Correct	679 ms	42984 KB	Output is correct
10	Correct	684 ms	42808 KB	Output is correct
11	Correct	699 ms	42552 KB	Output is correct
12	Correct	692 ms	42944 KB	Output is correct
13	Correct	682 ms	42776 KB	Output is correct
14	Correct	879 ms	43644 KB	Output is correct
15	Correct	915 ms	43924 KB	Output is correct
16	Correct	1010 ms	44484 KB	Output is correct
17	Correct	836 ms	43168 KB	Output is correct
18	Correct	827 ms	43228 KB	Output is correct
19	Correct	805 ms	43232 KB	Output is correct
20	Correct	782 ms	42840 KB	Output is correct
21	Correct	869 ms	42168 KB	Output is correct
22	Correct	873 ms	42056 KB	Output is correct
23	Correct	889 ms	44524 KB	Output is correct