oj.uz

Submission #577350

# Submission time Handle Problem Language Result Execution time Memory
577350 2022-06-14T15:09:51 Z jiahng Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 331060 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,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 122 ms 305612 KB Output is correct
2 Execution timed out 1586 ms 331024 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 305516 KB Output is correct
2 Correct 125 ms 305616 KB Output is correct
3 Correct 292 ms 305940 KB Output is correct
4 Correct 283 ms 305868 KB Output is correct
5 Correct 297 ms 305916 KB Output is correct
6 Correct 286 ms 305868 KB Output is correct
7 Correct 284 ms 305956 KB Output is correct
8 Correct 283 ms 305892 KB Output is correct
9 Correct 301 ms 305852 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 305516 KB Output is correct
2 Correct 125 ms 305616 KB Output is correct
3 Correct 292 ms 305940 KB Output is correct
4 Correct 283 ms 305868 KB Output is correct
5 Correct 297 ms 305916 KB Output is correct
6 Correct 286 ms 305868 KB Output is correct
7 Correct 284 ms 305956 KB Output is correct
8 Correct 283 ms 305892 KB Output is correct
9 Correct 301 ms 305852 KB Output is correct
10 Correct 127 ms 305548 KB Output is correct
11 Correct 127 ms 305496 KB Output is correct
12 Correct 292 ms 305916 KB Output is correct
13 Correct 299 ms 305924 KB Output is correct
14 Correct 321 ms 305948 KB Output is correct
15 Correct 293 ms 305876 KB Output is correct
16 Correct 286 ms 305996 KB Output is correct
17 Correct 294 ms 305956 KB Output is correct
18 Correct 292 ms 305740 KB Output is correct
19 Correct 1054 ms 309660 KB Output is correct
20 Execution timed out 1529 ms 309788 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 305516 KB Output is correct
2 Correct 125 ms 305616 KB Output is correct
3 Correct 292 ms 305940 KB Output is correct
4 Correct 283 ms 305868 KB Output is correct
5 Correct 297 ms 305916 KB Output is correct
6 Correct 286 ms 305868 KB Output is correct
7 Correct 284 ms 305956 KB Output is correct
8 Correct 283 ms 305892 KB Output is correct
9 Correct 301 ms 305852 KB Output is correct
10 Correct 122 ms 305612 KB Output is correct
11 Correct 128 ms 305600 KB Output is correct
12 Correct 287 ms 305860 KB Output is correct
13 Correct 290 ms 305924 KB Output is correct
14 Correct 284 ms 305876 KB Output is correct
15 Correct 293 ms 305848 KB Output is correct
16 Correct 289 ms 305868 KB Output is correct
17 Correct 287 ms 305828 KB Output is correct
18 Correct 290 ms 305964 KB Output is correct
19 Execution timed out 1601 ms 329728 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 1601 ms 331060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 305612 KB Output is correct
2 Execution timed out 1586 ms 331024 KB Time limit exceeded
3 Halted 0 ms 0 KB -