oj.uz

Submission #1111597

# Submission time Handle Problem Language Result Execution time Memory
1111597 2024-11-12T09:53:39 Z hmm789 Fire (BOI24_fire) C++14
34 / 100
 1898 ms 306736 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[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 < 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;
	n *= 2;
	pair<int, int> a[n];
	vector<int> dis, dis2, act;
	for(int i = 0; i < n; i++) {
		if(i < n/2) {
			cin >> x >> y;
			if(y < x) y = y+m;
			a[i] = {y, x};
			dis.push_back(x);
			dis.push_back(y);
		} else {
			a[i].first = a[i-n/2].first+m;
			a[i].second = a[i-n/2].second+m;
			dis.push_back(a[i].first);
			dis.push_back(a[i].second);
		}
	}
	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(i, -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:100: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]
  100 |  for(int i = 0; i < dis.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Main.cpp:120: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]
  120 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 147280 KB Output is correct
2 Correct 4 ms 19960 KB Output is correct
3 Incorrect 5 ms 19792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 147280 KB Output is correct
2 Correct 4 ms 19960 KB Output is correct
3 Incorrect 5 ms 19792 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 147280 KB Output is correct
2 Correct 4 ms 19960 KB Output is correct
3 Incorrect 5 ms 19792 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 5 ms 19792 KB Output is correct
2 Correct 21 ms 147016 KB Output is correct
3 Correct 20 ms 147024 KB Output is correct
4 Correct 21 ms 147040 KB Output is correct
5 Correct 20 ms 147024 KB Output is correct
6 Correct 6 ms 20052 KB Output is correct
7 Correct 5 ms 20048 KB Output is correct
8 Correct 21 ms 147280 KB Output is correct
9 Correct 21 ms 147280 KB Output is correct
10 Correct 20 ms 147280 KB Output is correct
11 Correct 21 ms 147280 KB Output is correct
12 Correct 20 ms 147280 KB Output is correct
13 Correct 30 ms 145232 KB Output is correct
14 Correct 24 ms 145232 KB Output is correct
15 Correct 55 ms 148816 KB Output is correct
16 Correct 43 ms 147672 KB Output is correct
17 Correct 29 ms 146656 KB Output is correct
18 Correct 52 ms 147624 KB Output is correct
19 Correct 52 ms 148552 KB Output is correct
20 Correct 99 ms 159664 KB Output is correct
21 Correct 1382 ms 290248 KB Output is correct
22 Correct 1340 ms 290088 KB Output is correct
23 Correct 1006 ms 251060 KB Output is correct
24 Correct 1898 ms 301712 KB Output is correct
25 Correct 497 ms 213940 KB Output is correct
26 Correct 905 ms 233396 KB Output is correct
27 Correct 1004 ms 251228 KB Output is correct
28 Correct 1285 ms 286056 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20048 KB Output is correct
2 Correct 19 ms 147252 KB Output is correct
3 Correct 22 ms 147040 KB Output is correct
4 Correct 19 ms 147280 KB Output is correct
5 Correct 4 ms 19936 KB Output is correct
6 Correct 4 ms 20048 KB Output is correct
7 Correct 4 ms 20048 KB Output is correct
8 Correct 20 ms 147272 KB Output is correct
9 Correct 20 ms 147280 KB Output is correct
10 Correct 20 ms 147248 KB Output is correct
11 Correct 20 ms 147280 KB Output is correct
12 Correct 46 ms 150600 KB Output is correct
13 Correct 31 ms 149772 KB Output is correct
14 Correct 30 ms 149204 KB Output is correct
15 Correct 78 ms 161720 KB Output is correct
16 Correct 941 ms 250800 KB Output is correct
17 Correct 1409 ms 295692 KB Output is correct
18 Correct 1325 ms 295724 KB Output is correct
19 Correct 1815 ms 306736 KB Output is correct
20 Correct 892 ms 234992 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 147280 KB Output is correct
2 Correct 4 ms 19960 KB Output is correct
3 Incorrect 5 ms 19792 KB Output isn't correct
4 Halted 0 ms 0 KB -