QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#262891 | #6531. Base Station Construction | Teal | WA | 59ms | 12704kb | C++14 | 2.2kb | 2023-11-24 11:26:21 | 2023-11-24 11:26:22 |
Judging History
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 || b < r) return inf;
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: 2ms
memory: 9728kb
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: 59ms
memory: 12704kb
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'