Submission #1308128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308128		thuhienne	Passport (JOI23_passport)	C++20	16 / 100	89 ms	60744 KiB

passport

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define thuhien ""
#define re exit(0);

const int inf = 1e9;

int n;
int l[200009],r[200009];

int minl[2509][2509],maxr[2509][2509],dp[2509][2509];

pair <int,int> uni(pair <int,int> a,pair <int,int> b) {
	return {min(a.first,b.first),max(a.second,b.second)};
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(nullptr);
	if (fopen(thuhien".inp","r")) {
	   freopen(thuhien".inp","r",stdin);
	   freopen(thuhien".out","w",stdout);
	}

	cin >> n;
	for (int i = 1;i <= n;i++) {
		cin >> l[i] >> r[i];
	}
	
	for (int i = n;i >= 1;i--) {
		minl[i][i] = maxr[i][i] = i;
		for (int j = i + 1;j <= n;j++) {
			int a = minl[i][j - 1];
			
			if (l[a] == l[j]) {
				minl[i][j] = r[a] > r[j] ? a : j;
			} else {
				minl[i][j] = l[a] < l[j] ? a : j;
			}
			
			a = maxr[i][j - 1];
			
			if (r[a] == r[j]) {
				maxr[i][j] = l[a] < l[j] ? a : j;
			} else {
				maxr[i][j] = r[a] > r[j] ? a : j;
			}
			
		}
	}
	
	for (int len = n - 1;len >= 1;len--) {
		for (int i = 1;i + len - 1 <= n;i++) {
			int left = i,right = i + len - 1;
			
			dp[left][right] = inf;
			
			int pos = minl[left][right];
			pair <int,int> temp = uni({left,right},{l[pos],r[pos]});
			dp[left][right] = min(dp[left][right],dp[temp.first][temp.second] + 1);
			
			pos = maxr[left][right];
			temp = uni({left,right},{l[pos],r[pos]});
			dp[left][right] = min(dp[left][right],dp[temp.first][temp.second] + 1);
			
		}
	}
	
	int q;cin >> q;while (q--) {
		int a;cin >> a;
		cout << (dp[a][a] > n ? -1 : dp[a][a]) << '\n';
	}

}

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:24:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |            freopen(thuhien".inp","r",stdin);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
passport.cpp:25:19: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |            freopen(thuhien".out","w",stdout);
      |            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 8
• Subtask 5: 0 / 46