oj.uz

답안 #577351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
577351 2022-06-14T15:15:34 Z jiahng Event Hopping (BOI22_events) C++14
10 / 100
 1500 ms 331432 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);
				}
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 305612 KB Output is correct
2 Execution timed out 1586 ms 331432 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 305556 KB Output is correct
2 Correct 143 ms 305624 KB Output is correct
3 Correct 296 ms 305876 KB Output is correct
4 Correct 291 ms 305868 KB Output is correct
5 Correct 313 ms 306040 KB Output is correct
6 Correct 293 ms 305812 KB Output is correct
7 Correct 307 ms 305896 KB Output is correct
8 Correct 327 ms 305940 KB Output is correct
9 Correct 293 ms 305752 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 305556 KB Output is correct
2 Correct 143 ms 305624 KB Output is correct
3 Correct 296 ms 305876 KB Output is correct
4 Correct 291 ms 305868 KB Output is correct
5 Correct 313 ms 306040 KB Output is correct
6 Correct 293 ms 305812 KB Output is correct
7 Correct 307 ms 305896 KB Output is correct
8 Correct 327 ms 305940 KB Output is correct
9 Correct 293 ms 305752 KB Output is correct
10 Correct 152 ms 305512 KB Output is correct
11 Correct 139 ms 305612 KB Output is correct
12 Correct 295 ms 305840 KB Output is correct
13 Correct 308 ms 305940 KB Output is correct
14 Correct 292 ms 306000 KB Output is correct
15 Correct 303 ms 305868 KB Output is correct
16 Correct 291 ms 305956 KB Output is correct
17 Correct 291 ms 306164 KB Output is correct
18 Correct 329 ms 305856 KB Output is correct
19 Correct 1062 ms 309712 KB Output is correct
20 Execution timed out 1551 ms 309692 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 123 ms 305556 KB Output is correct
2 Correct 143 ms 305624 KB Output is correct
3 Correct 296 ms 305876 KB Output is correct
4 Correct 291 ms 305868 KB Output is correct
5 Correct 313 ms 306040 KB Output is correct
6 Correct 293 ms 305812 KB Output is correct
7 Correct 307 ms 305896 KB Output is correct
8 Correct 327 ms 305940 KB Output is correct
9 Correct 293 ms 305752 KB Output is correct
10 Correct 144 ms 305616 KB Output is correct
11 Correct 124 ms 305572 KB Output is correct
12 Correct 290 ms 305940 KB Output is correct
13 Correct 307 ms 305868 KB Output is correct
14 Correct 292 ms 305944 KB Output is correct
15 Correct 313 ms 305884 KB Output is correct
16 Correct 297 ms 305936 KB Output is correct
17 Correct 325 ms 305892 KB Output is correct
18 Correct 291 ms 305852 KB Output is correct
19 Execution timed out 1607 ms 330152 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1571 ms 331264 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 120 ms 305612 KB Output is correct
2 Execution timed out 1586 ms 331432 KB Time limit exceeded
3 Halted 0 ms 0 KB -