QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#417639	#8718. 保区间最小值一次回归问题	light_ink_dots^#	WA	243ms	16060kb	C++14	3.0kb	2024-05-22 20:18:31	2024-05-22 20:18:34

Judging History

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

[2024-05-22 20:18:34]
评测

测评结果：WA
用时：243ms
内存：16060kb

查看

[2024-05-22 20:18:31]
提交

answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    static const int maxn = 500010;
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);
        static int a[maxn];
        for (int i = 1; i <= n; i++) scanf("%d", a + i);
        struct seg {
            int l, r, v;
        };
        static seg s[maxn];
        for (int i = 1; i <= m; i++) scanf("%d %d %d", &s[i].l, &s[i].r, &s[i].v);
        sort(s + 1, s + m + 1, [](const seg x, const seg y) { return x.v > y.v; });
        long long ans = 0;
        static int fa[maxn];
        for (int i = 1; i <= n + 1; i++) fa[i] = i;
        function<int(int)> find = [&find](const int u) { return u == fa[u] ? u : fa[u] = find(fa[u]); };
        for (int i = 1; i <= m; i++) {
            int j = i;
            vector<int> vec;
            while (j <= m && s[j].v == s[i].v) {
                int u = find(s[j].l);
                if (u > s[j].r) {
                    ans = -1;
                    break;
                }
                while (u <= s[j].r) vec.push_back(u), fa[u] = find(u + 1), u = find(u);
                j++;
            }
            if (ans == -1)
                break;
            sort(vec.begin(), vec.end());
            static int L[maxn];
            for (int i = 0; i < vec.size(); i++) L[i] = -1;
            int mxL = -1;
            for (int p = i; p < j; p++) {
                int l = lower_bound(vec.begin(), vec.end(), s[p].l) - vec.begin();
                int r = upper_bound(vec.begin(), vec.end(), s[p].r) - vec.begin() - 1;
                L[r] = max(L[r], l), mxL = max(mxL, l);
            }
            for (int i = 1; i < vec.size(); i++) L[i] = max(L[i], L[i - 1]);
            int V = s[i].v;
            long long mi = LLONG_MAX;
            static long long dp[maxn];
            for (int p : vec) ans += max(0, V - a[p]);
            struct BIT {
                int n;
                long long a[maxn];
                inline void init(const int n) {
                    this->n = n;
                    for (int i = 1; i <= n; i++) a[i] = LLONG_MAX >> 1;
                    return;
                }
                inline void insert(int p, long long x) {
                    for (int i = p + 1; i <= n; i += i & -i) a[i] = min(a[i], x);
                }
                inline long long query(int p) {
                    long long ret = LLONG_MAX >> 1;
                    for (int i = p + 1; i; i -= i & -i) ret = min(ret, a[i]);
                    return ret;
                }
            };
            static BIT t;
            t.init(vec.size());
            for (int i = 0; i < vec.size(); i++) {
                int D = a[vec[i]] > V ? a[vec[i]] - V : 0;
                dp[i] = !i || L[i - 1] == -1 ? 0 : t.query(L[i - 1]);
                t.insert(i, dp[i] += D);
                if (i >= mxL)
                    mi = min(mi, dp[i]);
            }
            ans += mi, i = j - 1;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 10104kb

input:

output:

result:

ok 1 number(s): "2"

Test #2:

score: -100

Wrong Answer

time: 243ms

memory: 16060kb

input:

1000
100 100
1 35141686 84105222 84105220 7273527 178494861 178494861 112519027 77833654 77833656 261586535 278472336 278472336 261586536 416361017 416361017 426649080 323519513 278472337 420127821 420127823 420127823 482516531 434108818 420127821 631535744 615930922 546346921 546346920 546346920 70...

output:

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
...

result:

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