Submission #1018934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018934		beaconmc	Fire (BOI24_fire)	C++14	40 / 100	2098 ms	12712 KiB

Main

#include <bits/stdc++.h>

typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)

using namespace std;

vector<vector<ll>> normal;
vector<vector<ll>> overlap;


int solve(ll lo, ll hi){
	ll ans = 0;
	ll cur = 0;
	while (lo < hi){
		ll maxi = 0;
		while (cur < normal.size()){
			if (normal[cur][0] > lo) break;
			maxi = max(maxi, normal[cur][1]);
			cur++;
		}

		if (maxi > lo) ans += 1, lo = maxi;
		else return 1000000000;
	}
	return ans;


}

int main(){
	ll n,m;
	cin >> n >> m;
	FOR(i,0,n){
		ll a,b;
		cin >> a >> b;
		if (a<b) normal.push_back({a,b});
		else overlap.push_back({b,a});
	}
	sort(normal.begin(), normal.end());
	ll ans = 1000000000;

	//check twice

	ll left = 0, right = m;
	for (auto&i : overlap) left = max(left, i[0]), right = min(right, i[1]);

	ans = min(ans, (ll)solve(left, right)+2);


	for (auto&i : overlap){
		ans = min(ans, (ll)solve(i[0], i[1]) + 1);
	}
	
	if (ans >= 1000000000) cout << -1;
	else cout << ans;




}

Compilation message (stderr)

Main.cpp: In function 'int solve(ll, ll)':
Main.cpp:18:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |   while (cur < normal.size()){
      |          ~~~~^~~~~~~~~~~~~~~

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