Submission #577349

#	Time	Username	Problem	Language	Result	Execution time	Memory
577349		jiahng	Event Hopping (BOI22_events)	C++14	25 / 100	1603 ms	331604 KiB

events

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ll int
//~ #define int ll
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 2000010
#define INF (ll)1e18
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,Q;
int S[maxn],E[maxn],s,e;

vpii queries[maxn];
const int sqrtn = 400;
vi A[maxn];

vi adj[maxn];
int par[maxn], twok[maxn][21];
bool vis[maxn];

struct node{
	int s,e,m,val,lazy=-2;
	node *l,*r;
	
	node(int ss,int ee){
		s = ss; e = ee; m = (s + e) / 2;
		if (s != e){
			l = new node(s,m); r = new node(m+1,e);
		}
	}
	void prop(){
		if (s == e || lazy == -2) return;
		l->val = r->val = l->lazy = r->lazy = lazy;
		lazy = -2;
	}
		
	void upd(int a,int b,int c){
		prop();
		if (a <= s && e <= b){
			val = lazy = c;
		}else if (a > e || s > b) return;
		else{
			l->upd(a,b,c); r->upd(a,b,c);
		}
	}
	int qry(int p){
		prop();
		if (s == e) return val;
		else if (p > m) return r->qry(p);
		else return l->qry(p);
	}
}*parseg;

void dfs(int x, int p){
	twok[x][0] = p;
	vis[x] = 1;
	FOR(i,1,20){
		if (twok[x][i-1] == -1) break;
		twok[x][i] = twok[twok[x][i-1]][i-1];
	}
	aFOR(i,adj[x]) dfs(i,x);
}
int ans[maxn];
void solve(){
	cin >> N >> Q;
	vi v;
	FOR(i,1,N){
		cin >> S[i] >> E[i];
		v.pb(S[i]); v.pb(E[i]);
	}
	sort(all(v)); v.erase(unique(all(v)), v.end());
	FOR(i,1,N){
		S[i] = lbd(v, S[i]) - v.begin() + 1;
		E[i] = lbd(v, E[i]) - v.begin() + 1;
	}
	FOR(i,1,N) A[E[i]].pb(i);
	//~ cout << A[7].size();
	//~ return;
	//~ FOR(i,1,N){
		//~ cout << S[i] << ' ' << E[i] << '\n';
	//~ }
	//~ return;
	FOR(i,1,Q){
		cin >> s >> e;
		if (s == e) ans[i] = 0;
		else if (S[e] <= E[s] && E[s] <= E[e]) ans[i] = 1;
		else queries[E[e]].pb(pii(pi(s,e), i));
	}

	parseg = new node(1,2*N);
	FOR(bkt, 0, 2*N/sqrtn){
		int l = bkt * sqrtn, r = min(2*N,l + sqrtn - 1);
		
		vpi v;
		FOR(i,1,l-1){
			aFOR(j, A[i]) v.pb(pi(S[j], E[j]));
		}
		// get par array by range max
		int mx = 0;
		sort(all(v));
		int vptr = 0;
		FOR(i,1,2*N) adj[i].clear();

		FOR(i,1,2*N){
			while (vptr < (int)v.size() && v[vptr].f == i){
				mx = max(mx, v[vptr].s);
				vptr++;
			}
			if (mx > i){
				parseg->upd(i,i,mx); adj[mx].pb(i);
			}else parseg->upd(i,i,-1);		
		}
		// get depths/twok
		
		mem(twok, -1); FOR(i,1,2*N) vis[i] = 0;
		DEC(i,2*N,1) if (!vis[i]) dfs(i,-1);
		
		// for(i,l,r){
		//  add ranges ending at i by range setting parent of [ss,ee] to i
		// 	process queries[i] by blifting out of unmarked nodes then dfs new
		
		
		int updlow = INF;
		FOR(i,l,r){
			aFOR(j,A[i]){
				parseg->upd(S[j],i-1,i);
				//~ cout << "UPDATE " << S[j] << ' ' << i-1 << '\n';
				updlow = min(updlow, S[j]);
			}
			//~ cout << i << '\n';
			//~ FOR(j,1,i) cout << parseg->qry(j) << ' ';
			//~ cout << '\n';
			aFOR(j,queries[i]){
				int x = E[j.f.f]; ans[j.s] = 0;
				DEC(k,20,0) if (twok[x][k] != -1 && twok[x][k] < updlow && twok[x][k] < S[j.f.s]){
					x = twok[x][k]; ans[j.s] += (1<<k);
				}
				while (1){
					int p = parseg->qry(x);
					//~ cout << p << ' ';
					if (p != -1 && p < S[j.f.s]){
						x = p; ans[j.s]++;
					}else break; 
				}
				//~ cout << "QUERY " << j.s << ' ' << x << ' ' << bkt << ' ' << l << ' ' << r << '\n';
				if (parseg->qry(x) == -1) ans[j.s] = -1;
				else ans[j.s] += 2;
			}
		}
	}
	FOR(i,1,Q){
		if (ans[i] == -1) cout << "impossible";
		else cout << ans[i];
		cout << '\n';
	}
}
				
int32_t main(){
	fast;
	//~ cin >> TC;
	//~ while (TC--) solve();
	solve();
}

• Subtask 1: 0 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30