oj.uz

Submission #1111582

# Submission time Handle Problem Language Result Execution time Memory
1111582 2024-11-12T09:46:36 Z hmm789 Fire (BOI24_fire) C++14
34 / 100
 747 ms 150328 KB 
#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[400000];
int p[400000][19], depth[400000];
bool v[400000];

void dfs(int x, int pa, int d) {
	v[x] = 1;
	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]) if(!v[i]) 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;
	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);
	}
	int cur = 0;
	while(par[cur] != cur) {
		cur = par[cur];
	}
	if(act[cur]-act[0] < m) {
		cout << -1 << '\n';
		return 0;
	}
	memset(p, -1, sizeof(p));
	for(int i = dis.size()-1; i >= 0; i--) if(!v[i]) {
		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

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:112: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]
  112 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72528 KB Output is correct
2 Correct 2 ms 11088 KB Output is correct
3 Incorrect 2 ms 11088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72528 KB Output is correct
2 Correct 2 ms 11088 KB Output is correct
3 Incorrect 2 ms 11088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72528 KB Output is correct
2 Correct 2 ms 11088 KB Output is correct
3 Incorrect 2 ms 11088 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11088 KB Output is correct
2 Correct 10 ms 72528 KB Output is correct
3 Correct 10 ms 72696 KB Output is correct
4 Correct 10 ms 72712 KB Output is correct
5 Correct 10 ms 72528 KB Output is correct
6 Correct 3 ms 11088 KB Output is correct
7 Correct 2 ms 11088 KB Output is correct
8 Correct 10 ms 72528 KB Output is correct
9 Correct 10 ms 72716 KB Output is correct
10 Correct 10 ms 72984 KB Output is correct
11 Correct 11 ms 72528 KB Output is correct
12 Correct 12 ms 72528 KB Output is correct
13 Correct 10 ms 72784 KB Output is correct
14 Correct 11 ms 72784 KB Output is correct
15 Correct 19 ms 74496 KB Output is correct
16 Correct 17 ms 73748 KB Output is correct
17 Correct 18 ms 73460 KB Output is correct
18 Correct 17 ms 73808 KB Output is correct
19 Correct 18 ms 74316 KB Output is correct
20 Correct 43 ms 79808 KB Output is correct
21 Correct 475 ms 142132 KB Output is correct
22 Correct 507 ms 144372 KB Output is correct
23 Correct 405 ms 123456 KB Output is correct
24 Correct 685 ms 147768 KB Output is correct
25 Correct 274 ms 108792 KB Output is correct
26 Correct 425 ms 114572 KB Output is correct
27 Correct 434 ms 123316 KB Output is correct
28 Correct 433 ms 141108 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11088 KB Output is correct
2 Correct 11 ms 72672 KB Output is correct
3 Correct 12 ms 72528 KB Output is correct
4 Correct 11 ms 72528 KB Output is correct
5 Correct 3 ms 11256 KB Output is correct
6 Correct 2 ms 11088 KB Output is correct
7 Correct 2 ms 11088 KB Output is correct
8 Correct 10 ms 72784 KB Output is correct
9 Correct 11 ms 72768 KB Output is correct
10 Correct 10 ms 72784 KB Output is correct
11 Correct 10 ms 72700 KB Output is correct
12 Correct 17 ms 74440 KB Output is correct
13 Correct 18 ms 73808 KB Output is correct
14 Correct 16 ms 73552 KB Output is correct
15 Correct 54 ms 79948 KB Output is correct
16 Correct 408 ms 123320 KB Output is correct
17 Correct 565 ms 144836 KB Output is correct
18 Correct 566 ms 146064 KB Output is correct
19 Correct 747 ms 150328 KB Output is correct
20 Correct 374 ms 115384 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 72528 KB Output is correct
2 Correct 2 ms 11088 KB Output is correct
3 Incorrect 2 ms 11088 KB Output isn't correct
4 Halted 0 ms 0 KB -