Submission #577520

#	Time	Username	Problem	Language	Result	Execution time	Memory
577520		jiahng	Event Hopping (BOI22_events)	C++14	100 / 100	887 ms	187464 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)1e9
#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 = 1000;
vi A[maxn];

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

struct node{
	int s,e,m;
	pi val = pi(INF,INF), lazy=pi(INF,INF);
	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 == pi(INF,INF)) return;
		l->lazy = min(l->lazy, lazy); r->lazy = min(r->lazy, lazy);
		l->val = min(l->val, lazy); r->val = min(r->val, lazy);
		lazy = pi(INF,INF);
	}
	void upd(int a,int b,pi c){
		prop();
		if (a <= s && e <= b){
			val = min(val, c); lazy = min(lazy, c);
		}else if (a > e || s > b) return;
		else{
			l->upd(a,b,c); r->upd(a,b,c);
			val = min(l->val, r->val);
		}
	}
	pi qry(int a,int b){
		prop();
		if (a <= s && e <= b) return val;
		else if (a > e || s > b) return pi(INF,INF);
		else return min(l->qry(a,b), r->qry(a,b));
	}
}*root;

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));
	//~ }

	root = new node(1,2*N);
	//~ root->upd(1,1,pi(1,1
	FOR(i,1,N) root->upd(E[i], E[i], pi(S[i], i));
	FOR(i,1,N){
		par[i] = root->qry(S[i], E[i]).s;
		if (par[i] == i) par[i] = -1;
		else adj[par[i]].pb(i);
		//~ cout << par[i] << ' ';
	}
	//~ cout << '\n';
	FOR(i,1,N) if (!vis[i]) dfs(i,-1);
	
	FOR(i,1,Q){
		cin >> s >> e;
		if (s == e) cout << 0;
		else if (S[e] <= E[s] && E[s] <= E[e]) cout << 1;
		else{
			int x = e, ans = 0;
			DEC(k,20,0) if (twok[x][k] != -1 && S[twok[x][k]] > E[s]){
				x = twok[x][k]; ans += (1<<k);
			}
			
			if (par[x] == -1) cout << "impossible";
			else{
				x = par[x];
				if (S[x] <= E[s] && E[s] <= E[x]) cout << ans + 2;
				else cout << "impossible";
			}
		}
		cout << '\n';
	}
}
				
int32_t main(){
	fast;
	//~ cin >> TC;
	//~ while (TC--) solve();
	solve();
}

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