oj.uz

Submission #1111567

# Submission time Handle Problem Language Result Execution time Memory
1111567 2024-11-12T09:39:53 Z hmm789 Fire (BOI24_fire) C++14
0 / 100
 330 ms 154560 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[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;
	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));
	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:90: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]
   90 |  for(int i = 0; i < dis.size(); i++) {
      |                 ~~^~~~~~~~~~~~
Main.cpp:108: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]
  108 |   for(int i = 0; i < dis.size()-1; i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34640 KB Output is correct
2 Correct 2 ms 5968 KB Output is correct
3 Incorrect 2 ms 5812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34640 KB Output is correct
2 Correct 2 ms 5968 KB Output is correct
3 Incorrect 2 ms 5812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34640 KB Output is correct
2 Correct 2 ms 5968 KB Output is correct
3 Incorrect 2 ms 5812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5968 KB Output is correct
2 Correct 5 ms 34640 KB Output is correct
3 Correct 5 ms 34640 KB Output is correct
4 Correct 6 ms 34720 KB Output is correct
5 Correct 5 ms 34640 KB Output is correct
6 Correct 2 ms 5968 KB Output is correct
7 Correct 2 ms 5968 KB Output is correct
8 Correct 5 ms 34640 KB Output is correct
9 Correct 5 ms 34640 KB Output is correct
10 Correct 7 ms 34640 KB Output is correct
11 Correct 5 ms 34640 KB Output is correct
12 Correct 5 ms 34640 KB Output is correct
13 Correct 6 ms 34640 KB Output is correct
14 Correct 6 ms 34800 KB Output is correct
15 Correct 13 ms 36432 KB Output is correct
16 Correct 12 ms 35920 KB Output is correct
17 Correct 9 ms 35408 KB Output is correct
18 Correct 12 ms 35920 KB Output is correct
19 Correct 12 ms 36432 KB Output is correct
20 Correct 37 ms 42048 KB Output is correct
21 Runtime error 330 ms 147384 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5968 KB Output is correct
2 Correct 5 ms 34832 KB Output is correct
3 Correct 5 ms 34640 KB Output is correct
4 Correct 5 ms 34684 KB Output is correct
5 Correct 2 ms 6144 KB Output is correct
6 Correct 2 ms 5968 KB Output is correct
7 Correct 2 ms 5968 KB Output is correct
8 Correct 6 ms 34640 KB Output is correct
9 Correct 5 ms 34640 KB Output is correct
10 Correct 5 ms 34640 KB Output is correct
11 Correct 5 ms 34640 KB Output is correct
12 Correct 12 ms 36432 KB Output is correct
13 Correct 13 ms 35920 KB Output is correct
14 Correct 10 ms 35664 KB Output is correct
15 Correct 43 ms 41912 KB Output is correct
16 Runtime error 299 ms 154560 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 34640 KB Output is correct
2 Correct 2 ms 5968 KB Output is correct
3 Incorrect 2 ms 5812 KB Output isn't correct
4 Halted 0 ms 0 KB -