oj.uz

답안 #1113866

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113866 2024-11-17T15:53:03 Z thelegendary08 Fire (BOI24_fire) C++17
0 / 100
 174 ms 76604 KB 
#include<bits/stdc++.h>
#define pb push_back
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<'\n'
#define dout(a) cout<<a<<' '<<#a<<'\n'
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<'\n'
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//ifstream cin(".in");
	//ofstream cout(".out");
	in2(n,m);
	vpii v;
	f0r(i,n){
		in2(a,b);
		v.pb({a,b});
	}
	sort(all(v));
	vpii w;
	int mx = -1;
	f0r(i, n){
		if(v[i].second + (v[i].first > v[i].second) * m > mx){
			w.pb(v[i]);
			mx = v[i].second + (v[i].first > v[i].second) * m;
		}
	}
	n = w.size();
	
	f0r(i, n){
		//out2(w[i].first, w[i].second);
	}
	
	bool ok = 1;
	f0r(i, n-1){
		if(w[i].first < w[i].second){
			if(!(w[i+1].first <= w[i].second && w[i].first <= w[i+1].first))ok = 0;
		}
		else{
			if(!(w[i+1].first >= w[i].first || w[i+1].first <= w[i].second))ok = 0;
		}
	}
	if(w[n-1].first < w[n-1].second || w[n-1].second < w[0].first)ok = 0;
	if(!ok || n < 2)out(-1);
	else{
		int ptr = 0;
		vi nxt(n);
		f0r(i, n){
			int save = ptr;
			if(w[i].first < w[i].second){
				while(w[i].first <= w[ptr].first && w[ptr].first <= w[i].second){
					ptr++;
					ptr %= n;
					if(ptr == save){
						break;
					}
				}
			}
			else{
				while(w[ptr].first >= w[i].first || w[ptr].first <= w[i].second){
					ptr++;
					ptr %= n;
					if(ptr == save)break;
				}
			}
			if(ptr != 0)nxt[i] = ptr - 1;
		
			else nxt[i] = n-1;
		}
		//vout(nxt);
		
		
		pii jmp[n][20];
		f0r(i, n){
			if(w[nxt[i]].first > w[nxt[i]].second){
				jmp[i][0] = {nxt[i], 1};
			}
			else jmp[i][0] = {nxt[i], 0};
		}
		FOR(i, 1, 20){
			f0r(j,n){
				jmp[j][i] = {jmp[jmp[j][i-1].first][i-1].first, (jmp[j][i-1].second + jmp[jmp[j][i-1].first][i-1].second)};
			}
		}
		f0r(i, n){
			//out2(jmp[i][0].first, jmp[i][0].second);
		}
		//out("");
		f0r(i, n){
			//out2(jmp[i][4].first, jmp[i][4].second);
		}
		
		int ans = 4e18;
		f0r(i, n){
			if(jmp[i][0].second == 1 && w[jmp[i][0].first].second >= w[i].first){
				ans = min(ans, 2ll);
			}
			else{
				int cur = 0;
				int dex = i;
				int loops = 0;
				for(int j = 19; j>=0; j--){
					if(loops == 0){
						if(jmp[dex][j].second == 1 && w[jmp[dex][j].first].second < w[i].first){
							cur += (1 << j);
							loops++;
							dex = jmp[dex][j].first;
							//out("path 1");
						}
						else if(jmp[dex][j].second == 0){
							cur += (1 << j);
							dex = jmp[dex][j].first;
							//out("path 2");
						}
					}
					else if(loops == 1){
						if(jmp[dex][j].second == 0 && w[jmp[dex][j].first].second < w[i].first){
							cur += (1 << j);
							dex = jmp[dex][j].first;
							//out("path 3");
						}
					}
					//dout2(loops, dex);
				}
				//out(cur);
				ans = min(ans, cur + 2);
			}
			
		}
		out(ans);
	}
	
	
}

Subtask #1
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Incorrect 1 ms 336 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 528 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 5 ms 2068 KB Output is correct
13 Correct 3 ms 2128 KB Output is correct
14 Correct 6 ms 2128 KB Output is correct
15 Correct 22 ms 6600 KB Output is correct
16 Correct 174 ms 75572 KB Output is correct
17 Incorrect 134 ms 76604 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 424 KB Output is correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Halted 0 ms 0 KB -