oj.uz

Submission #1113867

# Submission time Handle Problem Language Result Execution time Memory
1113867 2024-11-17T15:55:59 Z thelegendary08 Fire (BOI24_fire) C++17
0 / 100
 179 ms 72760 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);
			}
			
		}
		if(ans != 4e18)out(ans);
		else out(-1);
	}
	
	
}

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 Incorrect 1 ms 348 KB Output isn't correct
4 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 Incorrect 1 ms 348 KB Output isn't correct
4 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 Incorrect 1 ms 348 KB Output isn't correct
4 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 Correct 1 ms 508 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 508 KB Output is correct
10 Correct 1 ms 336 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 504 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 2 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 2128 KB Output is correct
13 Correct 4 ms 2312 KB Output is correct
14 Correct 4 ms 2128 KB Output is correct
15 Correct 22 ms 6600 KB Output is correct
16 Correct 179 ms 72760 KB Output is correct
17 Incorrect 144 ms 72756 KB Output isn't correct
18 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 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -