Submission #1111613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111613		hmm789	Fire (BOI24_fire)	C++14	100 / 100	923 ms	228132 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long 

struct node {
	int s, e, m, v, lz;
	node *l, *r;
	node(int _s, int _e) {
		s = _s, e = _e, m = (s+e)/2, v = 0, lz = -1;
		if(s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void prop() {
		if(lz == -1) return;
		v = lz;
		if(s != e) {
			l->lz = lz;
			r->lz = lz;
		}
		lz = -1;
	}
	void update(int x, int y, int val) {
		prop();
		if(x <= s && e <= y) {lz = val; return;}
		else if(x > m) r->update(x, y, val);
		else if(y <= m) l->update(x, y, val);
		else l->update(x, y, val), r->update(x, y, val);
		l->prop(); r->prop();
		v = max(l->v, r->v);
	}
	int get(int x) {
		prop();
		if(s == e) return v;
		else if(x > m) return r->get(x);
		else return l->get(x);
	}
} *root, *root2;

vector<int> adj[800000];
int p[800000][20], depth[800000];
bool v[800000];

void dfs(int x, int pa, int d) {
	v[x] = 1;
	depth[x] = d;
	p[x][0] = pa;
	for(int i = 1; i < 20; i++) {
		if(p[x][i-1] == -1) break;
		p[x][i] = p[p[x][i-1]][i-1];
	}
	for(int i : adj[x]) if(!v[i]) dfs(i, x, d+1);
}

int getp(int x, int k) {
	for(int i = 0; i < 20; i++) {
		if(k&(1<<i)) x = p[x][i];
	}
	return x;
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, x, y;
	cin >> n >> m;
	pair<int, int> a[n];
	vector<int> dis, dis2, act;
	for(int i = 0; i < n; i++) {
		cin >> x >> y;
		if(y < x) y = y+m;
		a[i] = {y, x};
		dis.push_back(x);
		dis.push_back(y);
	}
	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());
	for(int i : dis) act.push_back(i);
	root = new node(0, dis.size());
	
	for(int i = 0; i < n; i++) {
		a[i].first = lower_bound(dis.begin(), dis.end(), a[i].first)-dis.begin();
		a[i].second = lower_bound(dis.begin(), dis.end(), a[i].second)-dis.begin();
	}
	
	sort(a, a+n);
	for(int i = 0; i < n; i++) {
		root->update(a[i].second, a[i].first, a[i].first);
	}
	int par[dis.size()];
	for(int i = 0; i < dis.size(); i++) {
		if(root->get(i) != i) adj[root->get(i)].push_back(i);
		par[i] = root->get(i);
	}
	memset(p, -1, sizeof(p));
	for(int i = dis.size()-1; i >= 0; i--) if(!v[i]) {
		dfs(i, -1, 0);
	}
	int l = 0, r = n+1, md;
	while(l < r) {
		md = (l+r)/2;
		bool ok = false;
		for(int i = 0; i < dis.size()-1; i++) {
			if(act[getp(i, min(md, depth[i]))]-act[i] >= m) ok = true;
		}
		if(ok) r = md;
		else l = md+1;
	}
	if(l == n+1) cout << -1 << '\n';
	else cout << l << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:92:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for(int i = 0; i < dis.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Main.cpp:104:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~
Main.cpp:91:6: warning: variable 'par' set but not used [-Wunused-but-set-variable]
   91 |  int par[dis.size()];
      |      ^~~

• Subtask 1: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 21 / 21
• Subtask 6: 26 / 26