제출 #1321575

#제출 시각아이디문제언어결과실행 시간메모리
1321575thelegendary08Escape Route 2 (JOI24_escape2)C++17
100 / 100
810 ms177944 KiB
#include<bits/stdc++.h>
// #include<atcoder/modint>
// #include<atcoder/convolution>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
#define rs resize
#define ft front()
#define bk back()
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define r0f(i,n) for(int i = n-1; i >= 0; i--)
#define R0F(i,k,n) for(int i = n-1; i >= k; i--)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define SUM(v) (accumulate(all(v), 0LL))
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define YN(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
#define yn(x); if(x){cout<<"Yes"<<'\n';}else{cout<<"No"<<'\n';}
#define p2(x) (1LL << (x))
#define pct(x) (__builtin_popcountll((x)))
#define ist(x,y) (((x) >> (y)) & 1)
template<class T, class U> bool ckmin(T& a, const U& b) { return (T)b < a ? a = (T)b, 1 : 0; } 
template<class T, class U> bool ckmax(T& a, const U& b) { return a < (T)b ? a = (T)b, 1 : 0; } 
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
// using namespace atcoder; 
// using mint = modint998244353;
// using mint = modint1000000007;
const int mxn = 1e5 + 5; 
// mint fact[mxn], inv[mxn];
// mint C(int n, int r){return fact[n] * inv[n-r] * inv[r];}
// mint snb(int n, int r){return C(n + r, n);}
const int B = 1000, lg = 18;
struct item{
	int x, y, t; 
};
struct query{int l, r, t;};
struct segtree{
	vpii tree; int n; 
	segtree(int x){
		n=x; tree.rs(2*n+5);
	}
	void update(int k, int x){
		k+=n; tree[k]=mp(x,k-n); for(k/=2;k>=1;k/=2)tree[k]=min(tree[k*2],tree[k*2+1]);
	}
	int quer(int l, int r){
		pii ret = mp(4e18,0); l+=n;r+=n; while(l<=r){
			if(l%2==1)ckmin(ret,tree[l++]); if(r%2==0)ckmin(ret,tree[r--]); l/=2;r/=2;
		} return ret.S; 
	}
};
bool operator <(const query &a, const query &b){return a.r<b.r;}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	// fact[0]=1;FOR(i,1,mxn)fact[i]=fact[i-1]*i;inv[mxn-1]=fact[mxn-1].inv();r0f(i,mxn-1)inv[i]=inv[i+1]*(i+1);
	in2(n,T); vpii w[n-1]; vector<item>g[n-1]; int ptr = 0; f0r(i,n-1){
		in(m); f0r(j,m){in2(a,b); w[i].eb(a,b);} sort(rall(w[i])); 
		vpii tmp; for(auto [a,b] : w[i]){
			if(tmp.empty() || tmp.back().S > b)tmp.eb(a,b);
		} reverse(all(tmp)); for(auto [a,b] : tmp){g[i].pb({a,b,ptr}); ptr++;}
	} 
	int s = ptr; vvi ts(n-1); vpii nxt(s*2, mp(-1,0)), prev(s*2, mp(-1,0)); f0r(i,n-1)for(auto [x,y,t] : g[i]){
		nxt[t] = mp(t+s, y-x); prev[t+s] = mp(t, y-x); ts[i].pb(t);
	} 
	
	in(q); vector<query>quers; f0r(i,q){in2(l,r);l--;r--; quers.pb({l,r,i});} 
	vector<vector<query>>small(n); vector<query>big; for(auto [l,r,t] : quers){
		if(r-l+1 <= B)small[l].pb({l,r,t}); else big.pb({l,r,t});
	} 
	// f0r(i,n-1){
		// for(auto [x,y,z] : g[i])out3(x,y,z); cout<<'\n';
	// }
	// dout(s);
	f0r(i,n-2){
		int p1 = 0, p2 = 0; while(p1 < g[i].size()){
			int j = g[i][p1].t;
			if(g[i][p1].y > g[i+1].back().x){nxt[j+s] = mp(g[i+1][0].t, g[i+1][0].x - g[i][p1].y + T);}
			else{
				while(g[i+1][p2].x < g[i][p1].y)p2++; 
				nxt[j+s] = mp(g[i+1][p2].t, g[i+1][p2].x - g[i][p1].y);
			}
			p1++;
		}
		p1 = g[i].size() - 1, p2 = g[i+1].size() - 1; while(p2 >= 0){
			int j = g[i+1][p2].t; 
			if(g[i+1][p2].x < g[i][0].y){prev[j] = mp(g[i].back().t + s, g[i+1][p2].x - g[i].back().y + T);}
			else{
				while(g[i][p1].y > g[i+1][p2].x)p1--; 
				prev[j] = mp(g[i][p1].t + s, g[i+1][p2].x - g[i][p1].y); 
			}
			p2--;
		}
	}
	vector<vpii>R(s*2, vpii(lg)), L(s*2, vpii(lg)); f0r(i,s*2)R[i][0]=nxt[i], L[i][0]=prev[i]; FOR(j,1,lg)f0r(i,s*2){
		if(R[i][j-1].F==-1)R[i][j]=mp(-1,0); else if(R[R[i][j-1].F][j-1].F == -1)R[i][j]=mp(-1,0); else R[i][j]=mp(R[R[i][j-1].F][j-1].F, R[i][j-1].S + R[R[i][j-1].F][j-1].S);
		if(L[i][j-1].F==-1)L[i][j]=mp(-1,0); else if(L[L[i][j-1].F][j-1].F == -1)L[i][j]=mp(-1,0); else L[i][j]=mp(L[L[i][j-1].F][j-1].F, L[i][j-1].S + L[L[i][j-1].F][j-1].S);
	} 
	// f0r(i,10)cout<<nxt[i].F<<' '; cout<<'\n';
	vi ans(q);
	f0r(i,n){
		if(small[i].empty())continue; sort(all(small[i])); vi ptr, dist; for(auto u : ts[i])ptr.pb(u), dist.pb(0); 
		int jm = (small[i][0].r - small[i][0].l)*2-1; f0r(k,jm){f0r(j,ptr.size())dist[j]+=nxt[ptr[j]].S, ptr[j] = nxt[ptr[j]].F;}
		// vout(dist);
		ans[small[i][0].t] = *min_element(all(dist)); int pv = ans[small[i][0].t]; FOR(j,1,small[i].size()){
			f0r(k,(small[i][j].r - small[i][j-1].r) * 2){
				f0r(z,ptr.size())dist[z]+=nxt[ptr[z]].S, ptr[z]=nxt[ptr[z]].F;
			} if(small[i][j].r==small[i][j-1].r)ans[small[i][j].t]=pv; else ans[small[i][j].t]=*min_element(all(dist)), pv=ans[small[i][j].t]; //vout(dist);
		} 
	} 
	segtree S = segtree(n-1); f0r(i,n-1)S.update(i,g[i].size()); for(auto [l,r,t] : big){
		int d = S.quer(l,r-1); int lef = (d-l)*2; vi ptr, dist; for(auto u : ts[d])ptr.pb(u), dist.pb(0); f0r(j, lg)if(ist(lef,j)){
			f0r(i,ptr.size())dist[i]+=L[ptr[i]][j].S, ptr[i]=L[ptr[i]][j].F; 
		} //vout(dist);
		vi p2, d2; for(auto u : ts[d])p2.pb(u), d2.pb(0); int rig = (r-d)*2-1; f0r(j, lg)if(ist(rig, j)){
			f0r(i,ptr.size())d2[i]+=R[p2[i]][j].S, p2[i]=R[p2[i]][j].F;
		} f0r(i,ptr.size())d2[i]+=dist[i]; ans[t] = *min_element(all(d2));
	}
	f0r(i,q)cout<<ans[i]<<'\n';
	
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...