oj.uz

Submission #577355

# Submission time Handle Problem Language Result Execution time Memory
577355 2022-06-14T15:19:05 Z jiahng Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 333512 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 = 1000;
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 122 ms 305524 KB Output is correct
2 Execution timed out 1602 ms 333512 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 305624 KB Output is correct
2 Correct 131 ms 305572 KB Output is correct
3 Correct 159 ms 305872 KB Output is correct
4 Correct 155 ms 305860 KB Output is correct
5 Correct 189 ms 305828 KB Output is correct
6 Correct 155 ms 305928 KB Output is correct
7 Correct 156 ms 305860 KB Output is correct
8 Correct 160 ms 305824 KB Output is correct
9 Correct 157 ms 305836 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 305624 KB Output is correct
2 Correct 131 ms 305572 KB Output is correct
3 Correct 159 ms 305872 KB Output is correct
4 Correct 155 ms 305860 KB Output is correct
5 Correct 189 ms 305828 KB Output is correct
6 Correct 155 ms 305928 KB Output is correct
7 Correct 156 ms 305860 KB Output is correct
8 Correct 160 ms 305824 KB Output is correct
9 Correct 157 ms 305836 KB Output is correct
10 Correct 123 ms 305624 KB Output is correct
11 Correct 128 ms 305576 KB Output is correct
12 Correct 169 ms 305936 KB Output is correct
13 Correct 157 ms 305872 KB Output is correct
14 Correct 163 ms 305932 KB Output is correct
15 Correct 176 ms 305740 KB Output is correct
16 Correct 156 ms 305896 KB Output is correct
17 Correct 158 ms 305916 KB Output is correct
18 Correct 161 ms 305964 KB Output is correct
19 Correct 365 ms 309416 KB Output is correct
20 Execution timed out 1588 ms 309068 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 305624 KB Output is correct
2 Correct 131 ms 305572 KB Output is correct
3 Correct 159 ms 305872 KB Output is correct
4 Correct 155 ms 305860 KB Output is correct
5 Correct 189 ms 305828 KB Output is correct
6 Correct 155 ms 305928 KB Output is correct
7 Correct 156 ms 305860 KB Output is correct
8 Correct 160 ms 305824 KB Output is correct
9 Correct 157 ms 305836 KB Output is correct
10 Correct 130 ms 305596 KB Output is correct
11 Correct 127 ms 305596 KB Output is correct
12 Correct 163 ms 305924 KB Output is correct
13 Correct 161 ms 305828 KB Output is correct
14 Correct 160 ms 305868 KB Output is correct
15 Correct 164 ms 305872 KB Output is correct
16 Correct 169 ms 305856 KB Output is correct
17 Correct 176 ms 305836 KB Output is correct
18 Correct 160 ms 305756 KB Output is correct
19 Execution timed out 1556 ms 332184 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 1606 ms 333280 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 305524 KB Output is correct
2 Execution timed out 1602 ms 333512 KB Time limit exceeded
3 Halted 0 ms 0 KB -