Submission #1088615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088615		raczek	Fire (BOI24_fire)	C++17	40 / 100	2053 ms	91224 KiB

Main

#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 = par[i][0];
		int res = 2;
		bool e = 0;
		if(b == n) continue;
		while(!check(vals[i].first, vals[i].second, vals[b].second) && res <= n)
		{
			debug(b);
			e = 0;
			int d = 0;
			if(par[b][d] != n)
			{
				debug(d);
				//if(d == 0) break;
				e = true;
				res += (1<<(d+1))-1;
				b = par[b][d];	
			}
			else
				break;
		}
		debug(res);
		debug(e);
		if(e)
			result = min(result, res);
	}
	if(result > n)
		cout<<-1;
	else
		cout<<result;	
}

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