oj.uz

답안 #886430

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886430 2023-12-12T07:02:31 Z tsumondai Double Attendance (CCO22_day1problem3) C++14
15 / 25
 4 ms 7772 KB 
#include <bits/stdc++.h>
using namespace std;

#define Task "problemname"
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e9, mod = 1e9 + 7;

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, oo)) - 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});
}

void process() {
	cin >> n[0] >> n[1] >> k;
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= n[i]; j++) {
			cin >> a[i][j].fi >> a[i][j].se;
		}

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

	for (int i = 0; i < 2; i++) fill(dist[i], dist[i] + 600600, oo);
	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]*/ auto tmp = pq.top(); pq.pop();
		int d, t, c;
		d = tmp[0], t = tmp[1], c = tmp[2];
		if (d > dist[t][c]) continue;
		if (d > oo / 2) continue;
		ans = max(ans, c);


		int idx = getidx(t, d);

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


		int e = d + k;

		if (a[t][idx].first <= d && d < a[t][idx].second) {
			e = max(d + k, a[t][idx].second - k);
		}

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

	}

	cout << ans;
}
signed main() {
	cin.tie(0)->sync_with_stdio(false);
	if (fopen(Task".INP", "r")) {
		freopen(Task".INP", "r", stdin);
		freopen(Task".OUT", "w", stdout);
	}
	process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:92:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |   freopen(Task".INP", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:93:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |   freopen(Task".OUT", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7628 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7632 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 2 ms 7512 KB Output is correct
31 Correct 2 ms 7516 KB Output is correct
32 Correct 2 ms 7516 KB Output is correct
33 Correct 3 ms 7516 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7512 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7516 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7668 KB Output is correct
44 Correct 2 ms 7516 KB Output is correct
45 Correct 2 ms 7516 KB Output is correct
46 Correct 2 ms 7516 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7512 KB Output is correct
49 Correct 2 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7628 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7632 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 2 ms 7512 KB Output is correct
31 Correct 2 ms 7516 KB Output is correct
32 Correct 2 ms 7516 KB Output is correct
33 Correct 3 ms 7516 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7512 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7516 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7668 KB Output is correct
44 Correct 2 ms 7516 KB Output is correct
45 Correct 2 ms 7516 KB Output is correct
46 Correct 2 ms 7516 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7512 KB Output is correct
49 Correct 2 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct
52 Correct 2 ms 7516 KB Output is correct
53 Correct 2 ms 7516 KB Output is correct
54 Correct 2 ms 7516 KB Output is correct
55 Correct 2 ms 7516 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 3 ms 7516 KB Output is correct
58 Correct 3 ms 7512 KB Output is correct
59 Correct 3 ms 7516 KB Output is correct
60 Correct 2 ms 7516 KB Output is correct
61 Correct 2 ms 7628 KB Output is correct
62 Correct 2 ms 7516 KB Output is correct
63 Correct 2 ms 7516 KB Output is correct
64 Correct 3 ms 7516 KB Output is correct
65 Correct 2 ms 7516 KB Output is correct
66 Correct 3 ms 7516 KB Output is correct
67 Correct 3 ms 7512 KB Output is correct
68 Correct 3 ms 7516 KB Output is correct
69 Correct 3 ms 7516 KB Output is correct
70 Correct 3 ms 7516 KB Output is correct
71 Correct 3 ms 7512 KB Output is correct
72 Correct 2 ms 7516 KB Output is correct
73 Correct 2 ms 7516 KB Output is correct
74 Correct 2 ms 7516 KB Output is correct
75 Correct 2 ms 7516 KB Output is correct
76 Correct 2 ms 7632 KB Output is correct
77 Correct 2 ms 7516 KB Output is correct
78 Correct 3 ms 7516 KB Output is correct
79 Correct 3 ms 7516 KB Output is correct
80 Correct 4 ms 7516 KB Output is correct
81 Correct 4 ms 7516 KB Output is correct
82 Correct 2 ms 7512 KB Output is correct
83 Correct 3 ms 7516 KB Output is correct
84 Correct 3 ms 7516 KB Output is correct
85 Correct 3 ms 7684 KB Output is correct
86 Correct 2 ms 7516 KB Output is correct
87 Correct 2 ms 7516 KB Output is correct
88 Correct 2 ms 7516 KB Output is correct
89 Correct 2 ms 7516 KB Output is correct
90 Correct 2 ms 7516 KB Output is correct
91 Correct 2 ms 7772 KB Output is correct
92 Correct 2 ms 7384 KB Output is correct
93 Correct 2 ms 7516 KB Output is correct
94 Correct 2 ms 7516 KB Output is correct
95 Correct 2 ms 7512 KB Output is correct
96 Correct 2 ms 7516 KB Output is correct
97 Correct 2 ms 7516 KB Output is correct
98 Correct 2 ms 7516 KB Output is correct
99 Correct 2 ms 7516 KB Output is correct
100 Correct 2 ms 7516 KB Output is correct
101 Correct 2 ms 7516 KB Output is correct
102 Correct 2 ms 7516 KB Output is correct
103 Correct 2 ms 7516 KB Output is correct
104 Correct 2 ms 7516 KB Output is correct
105 Correct 2 ms 7516 KB Output is correct

Subtask #3
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7516 KB Output is correct
2 Incorrect 2 ms 7640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7516 KB Output is correct
3 Correct 2 ms 7516 KB Output is correct
4 Correct 2 ms 7516 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Correct 3 ms 7516 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 3 ms 7516 KB Output is correct
9 Correct 2 ms 7516 KB Output is correct
10 Correct 2 ms 7516 KB Output is correct
11 Correct 2 ms 7516 KB Output is correct
12 Correct 3 ms 7516 KB Output is correct
13 Correct 2 ms 7516 KB Output is correct
14 Correct 2 ms 7516 KB Output is correct
15 Correct 2 ms 7516 KB Output is correct
16 Correct 2 ms 7516 KB Output is correct
17 Correct 2 ms 7516 KB Output is correct
18 Correct 2 ms 7516 KB Output is correct
19 Correct 2 ms 7516 KB Output is correct
20 Correct 2 ms 7628 KB Output is correct
21 Correct 2 ms 7516 KB Output is correct
22 Correct 2 ms 7516 KB Output is correct
23 Correct 2 ms 7516 KB Output is correct
24 Correct 2 ms 7516 KB Output is correct
25 Correct 3 ms 7516 KB Output is correct
26 Correct 2 ms 7516 KB Output is correct
27 Correct 2 ms 7516 KB Output is correct
28 Correct 2 ms 7632 KB Output is correct
29 Correct 2 ms 7516 KB Output is correct
30 Correct 2 ms 7512 KB Output is correct
31 Correct 2 ms 7516 KB Output is correct
32 Correct 2 ms 7516 KB Output is correct
33 Correct 3 ms 7516 KB Output is correct
34 Correct 2 ms 7516 KB Output is correct
35 Correct 2 ms 7512 KB Output is correct
36 Correct 2 ms 7516 KB Output is correct
37 Correct 2 ms 7516 KB Output is correct
38 Correct 2 ms 7512 KB Output is correct
39 Correct 2 ms 7516 KB Output is correct
40 Correct 2 ms 7516 KB Output is correct
41 Correct 2 ms 7516 KB Output is correct
42 Correct 2 ms 7516 KB Output is correct
43 Correct 2 ms 7668 KB Output is correct
44 Correct 2 ms 7516 KB Output is correct
45 Correct 2 ms 7516 KB Output is correct
46 Correct 2 ms 7516 KB Output is correct
47 Correct 2 ms 7516 KB Output is correct
48 Correct 2 ms 7512 KB Output is correct
49 Correct 2 ms 7516 KB Output is correct
50 Correct 2 ms 7516 KB Output is correct
51 Correct 2 ms 7516 KB Output is correct
52 Correct 2 ms 7516 KB Output is correct
53 Correct 2 ms 7516 KB Output is correct
54 Correct 2 ms 7516 KB Output is correct
55 Correct 2 ms 7516 KB Output is correct
56 Correct 2 ms 7516 KB Output is correct
57 Correct 3 ms 7516 KB Output is correct
58 Correct 3 ms 7512 KB Output is correct
59 Correct 3 ms 7516 KB Output is correct
60 Correct 2 ms 7516 KB Output is correct
61 Correct 2 ms 7628 KB Output is correct
62 Correct 2 ms 7516 KB Output is correct
63 Correct 2 ms 7516 KB Output is correct
64 Correct 3 ms 7516 KB Output is correct
65 Correct 2 ms 7516 KB Output is correct
66 Correct 3 ms 7516 KB Output is correct
67 Correct 3 ms 7512 KB Output is correct
68 Correct 3 ms 7516 KB Output is correct
69 Correct 3 ms 7516 KB Output is correct
70 Correct 3 ms 7516 KB Output is correct
71 Correct 3 ms 7512 KB Output is correct
72 Correct 2 ms 7516 KB Output is correct
73 Correct 2 ms 7516 KB Output is correct
74 Correct 2 ms 7516 KB Output is correct
75 Correct 2 ms 7516 KB Output is correct
76 Correct 2 ms 7632 KB Output is correct
77 Correct 2 ms 7516 KB Output is correct
78 Correct 3 ms 7516 KB Output is correct
79 Correct 3 ms 7516 KB Output is correct
80 Correct 4 ms 7516 KB Output is correct
81 Correct 4 ms 7516 KB Output is correct
82 Correct 2 ms 7512 KB Output is correct
83 Correct 3 ms 7516 KB Output is correct
84 Correct 3 ms 7516 KB Output is correct
85 Correct 3 ms 7684 KB Output is correct
86 Correct 2 ms 7516 KB Output is correct
87 Correct 2 ms 7516 KB Output is correct
88 Correct 2 ms 7516 KB Output is correct
89 Correct 2 ms 7516 KB Output is correct
90 Correct 2 ms 7516 KB Output is correct
91 Correct 2 ms 7772 KB Output is correct
92 Correct 2 ms 7384 KB Output is correct
93 Correct 2 ms 7516 KB Output is correct
94 Correct 2 ms 7516 KB Output is correct
95 Correct 2 ms 7512 KB Output is correct
96 Correct 2 ms 7516 KB Output is correct
97 Correct 2 ms 7516 KB Output is correct
98 Correct 2 ms 7516 KB Output is correct
99 Correct 2 ms 7516 KB Output is correct
100 Correct 2 ms 7516 KB Output is correct
101 Correct 2 ms 7516 KB Output is correct
102 Correct 2 ms 7516 KB Output is correct
103 Correct 2 ms 7516 KB Output is correct
104 Correct 2 ms 7516 KB Output is correct
105 Correct 2 ms 7516 KB Output is correct
106 Correct 2 ms 7516 KB Output is correct
107 Incorrect 2 ms 7640 KB Output isn't correct
108 Halted 0 ms 0 KB -