Submission #760357

#	Time	Username	Problem	Language	Result	Execution time	Memory
760357		qwerasdfzxcl	Double Attendance (CCO22_day1problem3)	C++17	6 / 25	6 ms	5124 KiB

Main

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 2e9 + 200;
int n[2], k, dist[2][600600];
pair<int, int> a[2][300300];
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> pq;

int getidx(int t, int p){
	return upper_bound(a[t]+1, a[t]+n[t]+1, pair<int, int>(p, INF)) - a[t] - 1;
}

int calc(int t, int l, int r){
	int li = getidx(t, l), ri = getidx(t, r);
	return ri - li + (a[t][li].first <= l && l < a[t][li].second);
}

void push(int t, int c, int d){
	if (dist[t][c] <= d) return;
	dist[t][c] = d;
	pq.push({d, t, c});
}

int main(){
	scanf("%d %d %d", &n[0], &n[1], &k);
	for (int i=0;i<2;i++){
		for (int j=1;j<=n[i];j++){
			scanf("%d %d", &a[i][j].first, &a[i][j].second);
		}

		sort(a[i]+1, a[i]+n[i]+1);
	}

	for (int i=0;i<2;i++) fill(dist[i], dist[i]+600600, INF);
	if (a[0][1].first==0){
		dist[0][1] = 0;
		pq.push({0, 0, 1});
	}
	else{
		dist[0][0] = 0;
		pq.push({0, 0, 0});
	}

	int ans = 0;
	while(!pq.empty()){
		auto [d, t, c] = pq.top(); pq.pop();
		if (d > dist[t][c]) continue;
		// printf(" %d %d -> %d\n", t, c, d);
		if (d > INF / 2) continue;
		ans = max(ans, c);


		int idx = getidx(t, d);
		// printf("  idx = %d\n", idx);

		if (idx+1 <= n[t]){
			push(t, c+1, a[t][idx+1].first);
		}


		int e = d+k;

		push(t^1, c+calc(t^1, d+k, e), e);
		
	}

	printf("%d\n", ans);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |  scanf("%d %d %d", &n[0], &n[1], &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:29:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |    scanf("%d %d", &a[i][j].first, &a[i][j].second);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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