oj.uz

Submission #577349

# Submission time Handle Problem Language Result Execution time Memory
577349 2022-06-14T15:08:03 Z jiahng Event Hopping (BOI22_events) C++14
25 / 100
 1500 ms 331604 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 305504 KB Output is correct
2 Execution timed out 1603 ms 331508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 305612 KB Output is correct
2 Correct 128 ms 305584 KB Output is correct
3 Correct 216 ms 305944 KB Output is correct
4 Correct 245 ms 305856 KB Output is correct
5 Correct 214 ms 305820 KB Output is correct
6 Correct 216 ms 305900 KB Output is correct
7 Correct 214 ms 305876 KB Output is correct
8 Correct 216 ms 305992 KB Output is correct
9 Correct 211 ms 305892 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 305612 KB Output is correct
2 Correct 128 ms 305584 KB Output is correct
3 Correct 216 ms 305944 KB Output is correct
4 Correct 245 ms 305856 KB Output is correct
5 Correct 214 ms 305820 KB Output is correct
6 Correct 216 ms 305900 KB Output is correct
7 Correct 214 ms 305876 KB Output is correct
8 Correct 216 ms 305992 KB Output is correct
9 Correct 211 ms 305892 KB Output is correct
10 Correct 138 ms 305548 KB Output is correct
11 Correct 131 ms 305620 KB Output is correct
12 Correct 210 ms 305936 KB Output is correct
13 Correct 226 ms 305836 KB Output is correct
14 Correct 228 ms 305928 KB Output is correct
15 Correct 219 ms 305860 KB Output is correct
16 Correct 219 ms 305824 KB Output is correct
17 Correct 240 ms 305848 KB Output is correct
18 Correct 212 ms 305856 KB Output is correct
19 Correct 609 ms 309580 KB Output is correct
20 Correct 1377 ms 309900 KB Output is correct
21 Correct 1041 ms 310124 KB Output is correct
22 Correct 617 ms 309732 KB Output is correct
23 Correct 630 ms 309716 KB Output is correct
24 Correct 641 ms 309360 KB Output is correct
25 Correct 627 ms 309536 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 305612 KB Output is correct
2 Correct 128 ms 305584 KB Output is correct
3 Correct 216 ms 305944 KB Output is correct
4 Correct 245 ms 305856 KB Output is correct
5 Correct 214 ms 305820 KB Output is correct
6 Correct 216 ms 305900 KB Output is correct
7 Correct 214 ms 305876 KB Output is correct
8 Correct 216 ms 305992 KB Output is correct
9 Correct 211 ms 305892 KB Output is correct
10 Correct 130 ms 305828 KB Output is correct
11 Correct 128 ms 305524 KB Output is correct
12 Correct 217 ms 306016 KB Output is correct
13 Correct 211 ms 305828 KB Output is correct
14 Correct 213 ms 305908 KB Output is correct
15 Correct 214 ms 305888 KB Output is correct
16 Correct 214 ms 305848 KB Output is correct
17 Correct 224 ms 305916 KB Output is correct
18 Correct 211 ms 305808 KB Output is correct
19 Execution timed out 1569 ms 330760 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1602 ms 331604 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 305504 KB Output is correct
2 Execution timed out 1603 ms 331508 KB Time limit exceeded
3 Halted 0 ms 0 KB -