oj.uz

Submission #577347

# Submission time Handle Problem Language Result Execution time Memory
577347 2022-06-14T15:06:57 Z jiahng Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 332460 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 = 700;
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 171 ms 305564 KB Output is correct
2 Execution timed out 1609 ms 332308 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 305600 KB Output is correct
2 Correct 150 ms 305572 KB Output is correct
3 Correct 179 ms 306020 KB Output is correct
4 Correct 162 ms 305896 KB Output is correct
5 Correct 171 ms 305924 KB Output is correct
6 Correct 173 ms 305816 KB Output is correct
7 Correct 166 ms 305952 KB Output is correct
8 Correct 178 ms 305888 KB Output is correct
9 Correct 172 ms 305848 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 305600 KB Output is correct
2 Correct 150 ms 305572 KB Output is correct
3 Correct 179 ms 306020 KB Output is correct
4 Correct 162 ms 305896 KB Output is correct
5 Correct 171 ms 305924 KB Output is correct
6 Correct 173 ms 305816 KB Output is correct
7 Correct 166 ms 305952 KB Output is correct
8 Correct 178 ms 305888 KB Output is correct
9 Correct 172 ms 305848 KB Output is correct
10 Correct 128 ms 305584 KB Output is correct
11 Correct 132 ms 305548 KB Output is correct
12 Correct 163 ms 305904 KB Output is correct
13 Correct 193 ms 305828 KB Output is correct
14 Correct 165 ms 305892 KB Output is correct
15 Correct 169 ms 305772 KB Output is correct
16 Correct 167 ms 305952 KB Output is correct
17 Correct 164 ms 305884 KB Output is correct
18 Correct 175 ms 305812 KB Output is correct
19 Correct 465 ms 309648 KB Output is correct
20 Execution timed out 1595 ms 309348 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 305600 KB Output is correct
2 Correct 150 ms 305572 KB Output is correct
3 Correct 179 ms 306020 KB Output is correct
4 Correct 162 ms 305896 KB Output is correct
5 Correct 171 ms 305924 KB Output is correct
6 Correct 173 ms 305816 KB Output is correct
7 Correct 166 ms 305952 KB Output is correct
8 Correct 178 ms 305888 KB Output is correct
9 Correct 172 ms 305848 KB Output is correct
10 Correct 131 ms 305528 KB Output is correct
11 Correct 142 ms 305592 KB Output is correct
12 Correct 167 ms 305828 KB Output is correct
13 Correct 168 ms 306048 KB Output is correct
14 Correct 171 ms 305860 KB Output is correct
15 Correct 196 ms 305800 KB Output is correct
16 Correct 165 ms 305840 KB Output is correct
17 Correct 177 ms 305888 KB Output is correct
18 Correct 173 ms 305732 KB Output is correct
19 Execution timed out 1589 ms 332460 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 1604 ms 332348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 305564 KB Output is correct
2 Execution timed out 1609 ms 332308 KB Time limit exceeded
3 Halted 0 ms 0 KB -