제출 #1263515

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1263515		altern23	Event Hopping (BOI22_events)	C++20	0 / 100	12 ms	12612 KiB

events

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double

const int MAXN = 5e3;
const ll INF = 4e18;
const int MOD = 998244353;

ll S[MAXN + 5], E[MAXN + 5];
ll dp[MAXN + 5][MAXN + 5];
vector<pii> edges[MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;	
	// cin >> tc;
	for(;tc--;){
		ll N, Q; cin >> N >> Q;
		vector<pair<pii, ll>> segments(1);
		for(int i = 1; i <= N; i++){
			cin >> S[i] >> E[i];
			segments.push_back({{S[i], E[i]}, i});
		}
		sort(segments.begin(), segments.end());
		for(int i = 1; i <= N; i++){
			for(int j = i + 1; j <= N; j++){
				if(segments[j].fi.fi <= segments[i].fi.sec && segments[i].fi.sec <= segments[j].fi.sec){
					edges[i].push_back({segments[j].fi.sec, segments[j].sec});
					// cout << segments[i].sec << " " << segments[j].fi.sec << " edges\n";
				}
			}
			sort(edges[i].begin(), edges[i].end());
		}
		
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= N; j++) dp[i][j] = INF;
		}
		
		for(int len = 1; len <= N; len++){
			for(int j = 1; j <= N - len + 1; j++){
				ll L = j, R = j + len - 1;
				if(len == 1){
					dp[segments[L].sec][segments[R].sec] = 0;
				}
				else{
					if(segments[R].fi.fi <= segments[L].fi.sec && segments[L].fi.sec <= segments[R].fi.sec){
						dp[segments[L].sec][segments[R].sec] = 1;
					}
					else{
						// ambil segment terjauh, yang masih S[x] <= E[L] dan E[x] <= S[R]
						pii now = {segments[R].fi.sec, INF};
						auto it = upper_bound(edges[L].begin(), edges[L].end(), now);
						if(it != edges[L].begin()){
							--it;
							dp[segments[L].sec][segments[R].sec] = dp[(*it).sec][segments[R].sec] + 1;
						}
					}
				}
				// cout << dp[segments[L].sec][segments[R].sec] << " " << segments[L].sec << " " << segments[R].sec << "\n";
			}
		}	
		
		for(int i = 1; i <= Q; i++){
			ll a, b; cin >> a >> b;
			if(dp[a][b] >= INF) cout << "impossible\n";
			else cout << dp[a][b] << "\n";
		}
	}
}

/*

*/

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30