QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#262898#6531. Base Station ConstructionTealWA 49ms14488kbC++142.1kb2023-11-24 11:54:512023-11-24 11:54:52

Judging History

你现在查看的是最新测评结果

  • [2023-11-24 11:54:52]
  • 评测
  • 测评结果:WA
  • 用时:49ms
  • 内存:14488kb
  • [2023-11-24 11:54:51]
  • 提交

answer

#include <set>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N (500010)
#define inf (0x3f3f3f3f)
#define INF (0x3f3f3f3f3f3f3f3fll)
#define int long long
int T, n, m, a[N], dp[N], Min[N * 4];
struct Segment {
	int l, r;
	friend bool operator< (const Segment& a, const Segment& b) {
		return a.r == b.r ? a.l < b.l : a.r < b.r;
	}
} Seg[N];

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	while (ch < '0' || ch > '9')
		ch == '-' ? f = -1, ch = getchar() : ch = getchar();
	while (ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return x * f;
}

void build(int x, int l, int r) {
	Min[x] = INF;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x * 2, l, mid), build(x * 2 + 1, mid + 1, r);
}

void Modify(int x, int l, int r, int pos, int val) {
	if (l == r) {
		Min[x] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) Modify(x * 2, l, mid, pos, val);
	else Modify(x * 2 + 1, mid + 1, r, pos, val);
	Min[x] = min(Min[x * 2], Min[x * 2 + 1]);
} 

int Query(int x, int l, int r, int a, int b) {
	if (a <= l && r <= b) return Min[x];
	int mid = (l + r) >> 1;
	if (b <= mid) return Query(x * 2, l, mid, a, b);
	else if (a > mid) return Query(x * 2 + 1, mid + 1, r, a, b);
	else return min(Query(x * 2, l, mid, a, mid), Query(x * 2 + 1, mid + 1, r, mid + 1, b));
}

signed main() {
	// ios::sync_with_stdio(false);
	T = read();
	while (T--) {
		n = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		a[++n] = 0; // 统计答案使用
		m = read();
		for (int i = 1; i <= m; ++i) Seg[i].l = read(), Seg[i].r = read();
		sort(Seg + 1, Seg + m + 1);
		build(1, 1, n);
		int pre = 0;
		for (int i = 1; i <= n; ++i) {
			while (pre < m && Seg[pre + 1].r < i) pre++;
			int tmp = !pre ? 0 : Query(1, 1, n, Seg[pre].l, Seg[pre].r);
			dp[i] = tmp + a[i];
			// printf("%lld %lld %lld %lld %lld\n", i, Seg[pre].l, Seg[pre].r, tmp, dp[i]);
			Modify(1, 1, n, i, dp[i]);
		}
		// for (int i = 1; i <= n; ++i) printf("%d %d\n", i, dp[i]);
		printf("%lld\n", dp[n]);
	}
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9648kb

input:

2
5
3 2 4 1 100
3
1 3
2 4
5 5
5
7 3 4 2 2
3
1 4
2 3
4 5

output:

102
5

result:

ok 2 number(s): "102 5"

Test #2:

score: -100
Wrong Answer
time: 49ms
memory: 14488kb

input:

6201
12
88 78 46 95 84 98 55 3 68 42 6 18
19
6 9
10 11
12 12
8 11
8 12
2 3
2 3
1 5
9 9
7 8
6 11
2 4
12 12
2 4
2 9
7 10
8 8
1 7
6 11
5
76 27 48 66 61
2
1 4
3 5
8
64 81 20 6 86 9 4 55
1
7 7
9
1 43 18 81 11 22 9 61 83
14
5 6
2 6
5 8
1 4
9 9
9 9
7 7
2 5
8 9
5 6
4 8
5 8
9 9
6 6
10
66 41 84 7 80 31 22 96 ...

output:

73
48
4
95
303
141
23
170
159
139
131
194
95
68
230
93
109
89
120
130
143
27
1
193
36
93
239
303
152
150
177
57
46
18
24
66
83
160
108
62
35
122
111
81
115
111
45
211
94
7
94
86
272
244
262
87
302
81
86
16
30
129
40
91
60
179
81
88
142
97
77
111
110
247
211
53
65
17
213
101
184
137
171
24
194
153
10...

result:

wrong answer 1st numbers differ - expected: '141', found: '73'