Submission #1111544

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111544		hmm789	Fire (BOI24_fire)	C++14	0 / 100	1166 ms	463856 KiB

Main

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

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[200000];
int p[200000][18], depth[200000];

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

int getp(int x, int k) {
	for(int i = 0; i < 18; 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, mn = INF, mx = 0;
	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);
		dis2.push_back(x);
		dis2.push_back(x-1);
		dis2.push_back(x+1);
		dis2.push_back(y);
		dis2.push_back(y-1);
		dis2.push_back(y+1);
		mn = min(mn, x);
		mx = max(mx, y);
	}
	if(mx-mn < m) {
		cout << -1 << '\n';
		return 0;
	}
	sort(dis.begin(), dis.end());
	dis.erase(unique(dis.begin(), dis.end()), dis.end());
	sort(dis2.begin(), dis2.end());
	dis2.erase(unique(dis2.begin(), dis2.end()), dis2.end());
	for(int i : dis) act.push_back(i);
	root = new node(0, dis.size());
	root2 = new node(0, dis2.size());
	
	for(int i = 0; i < n; i++) {
		x = lower_bound(dis2.begin(), dis2.end(), a[i].second)-dis2.begin();
		y = lower_bound(dis2.begin(), dis2.end(), a[i].first)-dis2.begin();
		root2->update(x, y, 1);
		
		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);
	}
	for(int i = 1; i < dis2.size()-1; i++) if(!root2->get(i)) {
		cout << -1 << '\n';
		return 0;
	}
	for(int i = 0; i < dis.size(); i++) {
		if(root->get(i) != i) adj[root->get(i)].push_back(i);
	}
	memset(p, -1, sizeof(p));
	dfs(dis.size()-1, -1, 0);
	int l = 0, r = n, 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;
	}
	cout << l << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:109: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]
  109 |  for(int i = 1; i < dis2.size()-1; i++) if(!root2->get(i)) {
      |                 ~~^~~~~~~~~~~~~~~
Main.cpp:113: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]
  113 |  for(int i = 0; i < dis.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Main.cpp:122: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]
  122 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~

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