Submission #676506

#	Time	Username	Problem	Language	Result	Execution time	Memory
676506		penguin133	Osumnjičeni (COCI21_osumnjiceni)	C++17	110 / 110	806 ms	118076 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n, k, q;
int pos[200005], P[200005], L[200005], R[200005], vis[200005];
const int mod = 1e9  +7;
struct node{
	int s,e,m,val,lazy;
	node *l = nullptr, *r = nullptr;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)/2;
		val = lazy =0 ;
		if(s != e)l = new node(s, m), r = new node(m+1, e);
	}
	void propo(){
		if(lazy){
			val = lazy;
			if(s != e)l->lazy = lazy, r->lazy = lazy;
			lazy = 0;
		}
	}
	void upd(int a, int b,int c){
		if(s == a && e == b)lazy = c;
		else{
			if(b <= m)l->upd(a,b,c);
			else if(a > m)r->upd(a,b,c);
			else l->upd(a,m,c), r->upd(m+1,b,c);
			l->propo(), r->propo();
			val = max(l->val, r->val);
		}
	}
	int query(int a, int b){
		propo();
		if(l == nullptr || (s == a && e == b))return val;
		if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a,b);
		else return max(l->query(a,m ), r->query(m+1, b));
	}
}*root;
int ft[200005];
void upd(int l, int r, int v){
	r++;
	for(;r<=n;r+=(r & -r))ft[r] -= v;
	for(;l<=n;l+=(l& -l))ft[l] += v;
}
int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}
pii Q[200005];
//int ans[200005];
pi dis[200005];
pi A[400005];
int par[200005][20];
vector<int>v[200005];

void dfs(int x, int p){
	par[x][0] = p;
	for(auto i : v[x])dfs(i, x);
}

void solve(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> L[i] >> R[i];
		A[i] = {L[i], i}, A[n+i] = {R[i], i};
	}
	sort(A+1, A+2*n+1);
	root = new node(1, 2*n+1);
	int cnt = 0;
	for(int i=1;i<=2*n;i++){
		if(A[i].fi != A[i-1].fi)cnt++;
		if(dis[A[i].se].fi)dis[A[i].se].se = cnt;
		else dis[A[i].se].fi = cnt;
	}
	for(int i=1;i<=n;i++){
		pos[i] = root->query(dis[i].fi, dis[i].se);
		pos[i] = max(pos[i], pos[i-1]);
		root->upd(dis[i].fi, dis[i].se, i);
		v[pos[i]].push_back(i);
	}
	dfs(0, -1);
	for(int i=1;i<=19;i++){
		for(int j=0;j<=n;j++)par[j][i] = par[par[j][i-1]][i-1];
	}
	cin >> q;
	while(q--){
		int x,y;
		cin >> x >> y;
		int ans = 0;
		for(int i=19;i>=0;i--){
			if(par[y][i] >= x)y = par[y][i], ans += (1<<i);
		}
		cout << 1+ans << '\n';
	}
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

Main.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main(){
      | ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50