QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165863#5500. Barsarseny_y#WA 1249ms4396kbC++233.6kb2023-09-05 22:22:002023-09-05 22:22:00

Judging History

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

  • [2023-09-05 22:22:00]
  • 评测
  • 测评结果:WA
  • 用时:1249ms
  • 内存:4396kb
  • [2023-09-05 22:22:00]
  • 提交

answer

//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

typedef long long ll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    std::sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(std::unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    std::reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

using namespace std;

const int K = 1488;

#define int ll

mt19937 rnd(228);

int R = 1;

struct Tree {
    vector<int> t, psh;

    Tree() {
        t.resize(R * 2, -1), psh.resize(R * 2, -1);
    }

    void push(int node) {
        if (psh[node] == -1) {
            return;
        }
        for (int i = node * 2; i <= node * 2 + 1; ++i) {
            t[i] = psh[node], psh[i] = psh[node];
        }
        psh[node] = -1;
    }

    void update(int ql, int qr, int nv, int node = 1, int nl = 1, int nr = R) {
        if (ql <= nl && nr <= qr) {
            psh[node] = nv, t[node] = nv;
            return;
        }
        if (qr < nl || nr < ql) {
            return;
        }
        int nm = (nr + nl) / 2;
        push(node);
        update(ql, qr, nv, node * 2, nl, nm), update(ql, qr, nv, node * 2 + 1, nm + 1, nr);
    }

    int gett(int ind, int node = 1, int nl = 1,int nr = R) {
        if (nl == nr) return t[node];
        int nm = (nr + nl) / 2;
        push(node);
        if (nl <= ind && ind <= nm) {
            return gett(ind, node * 2, nl, nm);
        } else {
            return gett(ind, node * 2 + 1, nm + 1, nr);
        }
    }
};

int32_t main() {
    std::cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    ll t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        R = 1;
        while (R <= n) R <<= 1;
        vector<int> a(n);
        for (auto &i : a) {
            cin >> i;
        }
        vector<int> dp(n + 1, 0);
        a.insert(a.begin(), 0);
        int mx = (n - 1) * a[1];
        Tree tree;
        auto get = [&](int i) -> int {
            int wasi = tree.gett(i);
            if (wasi == -1) return 0;
            assert(i > wasi);
            return dp[wasi] + (i - wasi) * (a[wasi] + a[i]);
        };
        for (int i = 1; i <= n; ++i) {
            dp[i] = get(i);
            mx = max(mx, (n - i) * a[i] + dp[i]);
            int l = i, r = n + 1;
            while (r - l > 1) {
                int mid = (l + r) / 2;
                int cur = dp[i] + (mid - i) * (a[i] + a[mid]);
                dp[mid] = get(mid);
                if (mid == i) {
                    l = mid;
                    continue;
                }
                if (cur >= dp[mid]) {
                    l = mid;
                } else {
                    r = mid;
                }
            }
            if (l >= i + 1) {
                tree.update(i + 1, l, i);
            }
//            for (int j = i + 1; j <= l; ++j) {
//                int cur = dp[i] + (j - i) * (a[i] + a[j]);
//                if (cur >= dp[j]) {
//                    cerr << j << ' ';
//                    dp[j] = cur;
//                } else {
//                    break;
//                }
//            }
//            cerr << "\n";
        }
        cout << mx << "\n";
    }
}

详细

Test #1:

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

input:

2
4
5 2 2 6
5
1 5 4 4 1

output:

33
29

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 1249ms
memory: 4396kb

input:

10000
4
5 2 2 6
5
1 5 4 4 1
197
763787596 15221694 898228999 187472305 466351873 822742732 437754202 800092772 843092246 915675776 166265020 346340615 796714085 497548541 182089610 64356048 363276768 181268733 257949015 236568898 752096761 928725929 443146784 114577469 833053207 38120723 14891030 41...

output:

33
29
344196372073
628489725924
527715094686
458946673513
296420749955
722426437868
605517922670
498810208980
225238172700
672692173377
466644027129
268377978633
585094154153
187324600073
336548832140
416875812294
511129819369
555848480782
382458165183
684444247516
879006539301
756294719596
26408806...

result:

wrong answer 3rd lines differ - expected: '382465638565', found: '344196372073'