oj.uz

Submission #577518

# Submission time Handle Problem Language Result Execution time Memory
577518 2022-06-15T03:39:58 Z jiahng Event Hopping (BOI22_events) C++14
20 / 100
 926 ms 186492 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)1e9
#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;
	pi val = pi(INF,INF), lazy=pi(INF,INF);
	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 == pi(INF,INF)) return;
		l->lazy = min(l->lazy, lazy); r->lazy = min(r->lazy, lazy);
		l->val = min(l->val, lazy); r->val = min(r->val, lazy);
		lazy = pi(INF,INF);
	}
	void upd(int a,int b,pi c){
		prop();
		if (a <= s && e <= b){
			val = min(val, c); lazy = min(lazy, c);
		}else if (a > e || s > b) return;
		else{
			l->upd(a,b,c); r->upd(a,b,c);
			val = min(l->val, r->val);
		}
	}
	pi qry(int a,int b){
		prop();
		if (a <= s && e <= b) return val;
		else if (a > e || s > b) return pi(INF,INF);
		else return min(l->qry(a,b), r->qry(a,b));
	}
}*root;

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));
	//~ }

	root = new node(1,2*N);
	//~ root->upd(1,1,pi(1,1
	FOR(i,1,N) root->upd(S[i], E[i], pi(S[i], i));
	FOR(i,1,N){
		par[i] = root->qry(S[i], E[i]).s;
		if (par[i] == i) par[i] = -1;
		else adj[par[i]].pb(i);
		//~ cout << par[i] << ' ';
	}
	cout << '\n';
	FOR(i,1,N) if (!vis[i]) dfs(i,-1);
	
	FOR(i,1,Q){
		cin >> s >> e;
		if (s == e) cout << 0;
		else if (S[e] <= E[s] && E[s] <= E[e]) cout << 1;
		else{
			int x = e, ans = 0;
			DEC(k,20,0) if (twok[x][k] != -1 && S[twok[x][k]] > E[s]){
				x = twok[x][k]; ans += (1<<k);
			}
			
			if (par[x] == -1) cout << "impossible";
			else{
				x = par[x];
				if (S[x] <= E[s] && E[s] <= E[x]) cout << ans + 2;
				else cout << "impossible";
			}
		}
		cout << '\n';
	}
}
				
int32_t main(){
	fast;
	//~ cin >> TC;
	//~ while (TC--) solve();
	solve();
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 141188 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 141168 KB Output is correct
2 Incorrect 72 ms 141140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 141168 KB Output is correct
2 Incorrect 72 ms 141140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 141168 KB Output is correct
2 Incorrect 72 ms 141140 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 846 ms 186480 KB Output is correct
2 Correct 666 ms 186488 KB Output is correct
3 Correct 926 ms 186492 KB Output is correct
4 Correct 306 ms 180836 KB Output is correct
5 Correct 565 ms 185272 KB Output is correct
6 Correct 605 ms 183648 KB Output is correct
7 Correct 643 ms 183544 KB Output is correct
8 Correct 640 ms 182132 KB Output is correct
9 Correct 526 ms 180544 KB Output is correct
10 Correct 633 ms 183168 KB Output is correct
11 Correct 603 ms 182252 KB Output is correct
12 Correct 646 ms 183236 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 71 ms 141188 KB Output isn't correct
2 Halted 0 ms 0 KB -