oj.uz

Submission #1111562

# Submission time Handle Problem Language Result Execution time Memory
1111562 2024-11-12T09:36:58 Z Ruichen Fire (BOI24_fire) C++17
0 / 100
 1 ms 516 KB 
#include <bits/stdc++.h>
using namespace std;

struct shift{
	int s, e;
	const bool operator<(const shift &t) const{if(s==t.s){return e<t.e;}return s<t.s;}
};

int main(){
	int n, m, li, lt=0;
	cin >> n >> m;
	vector<shift> v(n);
	for(int i=0; i<n; i++){
		cin >> v[i].s >> v[i].e;
	}
	sort(v.begin(),v.end());
	for(int i=0; i<n; i++){
		if((v[i].e-v[i].s+m)%m>lt){
			lt=(v[i].e-v[i].s+m)%m;
			li=i;
		}
	}
	priority_queue<int> pq;
	if(v[li].e<v[li].s){
		v[li].e+=m;
	}
	int pf=v[li].e, p=(li+1)%n, ans=1;
	while(pf<v[li].s+m){
		while(v[p].s<=pf&&p<li){
			if((v[p].s<v[li].s&&v[p].s+m<=pf)||v[p].s>v[li].s){
				if(v[p].e<v[li].s||v[p].s<v[li].s){
					pq.push(v[p].e+m);
				}
				else{
					pq.push(v[p].e);
				}
				//cout << p << " " << v[p].e << " " << pf << endl;
				p++;
				p%=n;
			}
			else{
				break;
			}
		}
		if(pq.empty()||pq.top()<=pf){
			cout << -1 << endl;
			return 0;
		}
		else{
			ans++;
			pf=pq.top();
			pq.pop();
		}
	}
	cout << ans << endl;
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:29:19: warning: 'li' may be used uninitialized in this function [-Wmaybe-uninitialized]
   29 |   while(v[p].s<=pf&&p<li){

Subtask #1
0 / 14.0

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

Subtask #2
0 / 17.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

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