oj.uz

Submission #577354

# Submission time Handle Problem Language Result Execution time Memory
577354 2022-06-14T15:17:32 Z jiahng Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 331196 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 = 200;
vi A[maxn];

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

struct node{
	int s,e,m,val=-1,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){
			int p = parseg->qry(i);
			if (p != -1) adj[p].pb(i);
		}
		//~ 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);
				}
				int co = 0;
				while (1){
					int p = parseg->qry(x);
					//~ cout << p << ' ';
					if (p != -1 && p < S[j.f.s]){
						x = p; ans[j.s]++; co++;
					}else break; 
				}
				assert(co <= sqrtn);
				//~ 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 124 ms 305560 KB Output is correct
2 Execution timed out 1594 ms 331128 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 305612 KB Output is correct
2 Correct 129 ms 305520 KB Output is correct
3 Correct 292 ms 305896 KB Output is correct
4 Correct 301 ms 305912 KB Output is correct
5 Correct 295 ms 306036 KB Output is correct
6 Correct 309 ms 305860 KB Output is correct
7 Correct 282 ms 305948 KB Output is correct
8 Correct 298 ms 305864 KB Output is correct
9 Correct 301 ms 305740 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 305612 KB Output is correct
2 Correct 129 ms 305520 KB Output is correct
3 Correct 292 ms 305896 KB Output is correct
4 Correct 301 ms 305912 KB Output is correct
5 Correct 295 ms 306036 KB Output is correct
6 Correct 309 ms 305860 KB Output is correct
7 Correct 282 ms 305948 KB Output is correct
8 Correct 298 ms 305864 KB Output is correct
9 Correct 301 ms 305740 KB Output is correct
10 Correct 129 ms 305532 KB Output is correct
11 Correct 129 ms 305580 KB Output is correct
12 Correct 309 ms 305916 KB Output is correct
13 Correct 323 ms 305912 KB Output is correct
14 Correct 303 ms 305912 KB Output is correct
15 Correct 291 ms 305944 KB Output is correct
16 Correct 307 ms 305816 KB Output is correct
17 Correct 303 ms 305884 KB Output is correct
18 Correct 299 ms 305952 KB Output is correct
19 Correct 1024 ms 309648 KB Output is correct
20 Execution timed out 1523 ms 309648 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 305612 KB Output is correct
2 Correct 129 ms 305520 KB Output is correct
3 Correct 292 ms 305896 KB Output is correct
4 Correct 301 ms 305912 KB Output is correct
5 Correct 295 ms 306036 KB Output is correct
6 Correct 309 ms 305860 KB Output is correct
7 Correct 282 ms 305948 KB Output is correct
8 Correct 298 ms 305864 KB Output is correct
9 Correct 301 ms 305740 KB Output is correct
10 Correct 131 ms 305612 KB Output is correct
11 Correct 141 ms 305516 KB Output is correct
12 Correct 304 ms 305948 KB Output is correct
13 Correct 309 ms 306024 KB Output is correct
14 Correct 302 ms 305932 KB Output is correct
15 Correct 292 ms 305868 KB Output is correct
16 Correct 291 ms 305940 KB Output is correct
17 Correct 333 ms 305888 KB Output is correct
18 Correct 288 ms 305848 KB Output is correct
19 Execution timed out 1601 ms 329880 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 1575 ms 331196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 305560 KB Output is correct
2 Execution timed out 1594 ms 331128 KB Time limit exceeded
3 Halted 0 ms 0 KB -