oj.uz

Submission #760356

# Submission time Handle Problem Language Result Execution time Memory
760356 2023-06-17T13:38:04 Z qwerasdfzxcl Double Attendance (CCO22_day1problem3) C++17
0 / 25
 6 ms 5120 KB 
#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);
		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

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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4916 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 5 ms 5076 KB Output is correct
4 Correct 4 ms 5056 KB Output is correct
5 Correct 6 ms 5076 KB Output is correct
6 Correct 5 ms 5076 KB Output is correct
7 Correct 5 ms 5076 KB Output is correct
8 Incorrect 5 ms 5120 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4948 KB Output is correct
2 Incorrect 3 ms 4948 KB Output isn't correct
3 Halted 0 ms 0 KB -