oj.uz

Submission #1088628

# Submission time Handle Problem Language Result Execution time Memory
1088628 2024-09-14T17:18:19 Z raczek Fire (BOI24_fire) C++17
0 / 100
 10 ms 16848 KB 
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator <<(auto& o, pair<auto, auto> p) {return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator <<(auto& o, auto x)->decltype(x.end(), o) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cout<<"["#X"]"<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
const int base = 1<<19;
struct segtree
{
	vector<pair<int, int> > tree;
	segtree(int n){tree.resize(base*2+10, {0, -n});}
	void add(int w, pair<int, int> val)
	{
		w += base;
		if(tree[w] < val) tree[w] = val;
		w /= 2;
		while(w != 0)
		{
			tree[w] = max(tree[w*2], tree[w*2+1]);
			w /= 2;
		}
	}
	pair<int, int> query(int w, int p, int k, int x, int y)
	{
		if(p > y || k < x) return {0, -1};
		if(x <= p && k <= y) return tree[w];
		return max(query(w*2, p, (p+k)/2, x, y),
				query(w*2+1, (p+k)/2+1, k, x, y));
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m;
	cin>>n>>m;
	map<int, int> scl;
	vector<pair<int, int> > vals(n);
	for(auto& v : vals) cin>>v.first>>v.second;
	for(auto& v : vals) scl[v.first] = 1, scl[v.second] = 1;
	int cnt = 0;
	for(auto& v : scl) v.second = cnt++;
	for(auto& v : vals) v.first = scl[v.first], v.second = scl[v.second];
	debug(vals);
	segtree A(n);
	for(auto& v : vals)
		if(v.second < v.first)
		{A.add(v.first, make_pair(v.second + cnt, -(int)(&v - &vals[0])));}
		else
		{A.add(v.first, make_pair(v.second, -(int)(&v - &vals[0])));}
	vector par(n+1, vector(20, n));
	for(auto& v : vals)
	{
		debug((int)(&v - &vals[0]));
		if(v.second < v.first)
		{
			auto a1 = A.query(1, 0, base-1, v.first, base-1);
			auto a2 = A.query(1, 0, base-1, 0, v.second);
			if(a2.second != -1){par[(int)(&v - &vals[0])][0] = -a2.second;}
			else par[(int)(&v - &vals[0])][0] = -a1.second;
		}
		else
			par[(int)(&v - &vals[0])][0] =
				-A.query(1, 0, base-1, v.first, v.second).second;
	}
	int result = 1e9+7;
	auto check = [&](int p, int k, int x)
	{
		if(x < 0) return false;
		if(k < p)
			return x >= p || x <= k;
		else
			return p <= x && x <= k;
	};
	vals.push_back({-1, -1});
	for(int i=0;i<n;i++) 
		if(par[i][0] != i &&
				par[i][0] != n &&
				check(vals[i].first, vals[i].second, vals[par[i][0]].second))
		{cout<<2; return 0;}
	for(int i=1;i<20;i++)
		for(int j=0;j<n;j++)
		{
			par[j][i] = par[par[j][i-1]][i-1];
			if(check(vals[j].first, vals[j].second, vals[par[j][i]].second))
			{
				if(par[j][i] != j)
					result = min(result, (1LL<<(i+1))); 
				par[j][i] = n;
			}
		}
	debug(par);
	for(int i=0;i<n;i++)
	{
		int b = i;
		int res = 1;
		bool e = true;
		while(e)
		{
			if(i == 1) debug(b);
			e = false;
			int d = 0;
			for(;d<20;d++)
			{
				if(par[b][d] == n) break;
				if(par[b][d] == b) break;
				if(!check((vals[b].second)%cnt, (vals[i].first-1+cnt)%cnt, vals[par[b][d]].second)) 
				break;
			}
			if(d == 0) break;
			d--;
			b = par[b][d];
			if(i == 1) debug(d);
			res += (1<<d);
			e = true;
		}
		if(par[b][0] != n && par[b][0] != b)
		result = min(result, res+1);
	}
	if(result > n)
		cout<<-1;
	else
		cout<<result;	
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 6 ms 16840 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 10 ms 16664 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Incorrect 6 ms 16732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 6 ms 16840 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 10 ms 16664 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Incorrect 6 ms 16732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 6 ms 16840 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 10 ms 16664 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Incorrect 6 ms 16732 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16728 KB Output is correct
2 Correct 6 ms 16820 KB Output is correct
3 Incorrect 6 ms 16848 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 16732 KB Output is correct
2 Correct 6 ms 16840 KB Output is correct
3 Correct 7 ms 16732 KB Output is correct
4 Correct 6 ms 16732 KB Output is correct
5 Correct 10 ms 16664 KB Output is correct
6 Correct 6 ms 16732 KB Output is correct
7 Correct 6 ms 16732 KB Output is correct
8 Correct 6 ms 16732 KB Output is correct
9 Incorrect 6 ms 16732 KB Output isn't correct
10 Halted 0 ms 0 KB -