QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#305413#8006. Dinosaur Bones Diggingucup-team1516WA 1ms3788kbC++142.8kb2024-01-15 10:55:512024-01-15 10:55:52

Judging History

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

  • [2024-01-15 10:55:52]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3788kb
  • [2024-01-15 10:55:51]
  • 提交

answer

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) { return (ull)rng() % B; }
inline double time() {
    return static_cast<long double>(
               chrono::duration_cast<chrono::nanoseconds>(
                   chrono::steady_clock::now().time_since_epoch())
                   .count()) *
           1e-9;
}

template <class S, S (*op)(S, S), S (*e)()> struct segtree {
    int n;
    vector<S> tree;
    segtree() : segtree(0) {}
    segtree(int n) : n(n), tree(vector<S>(n << 1, e())) {}
    // 未verify(え?)
    segtree(const vector<S> &v) : n((int)v.size()) {
        tree.resize(n * 2);
        for (int i = 0; i < n; ++i) {
            tree[n + i] = v[i];
        }
        for (int i = n - 1; i >= 1; --i) {
            update(i);
        }
    }
    void update(int k) { tree[k] = op(tree[k << 1 | 0], tree[k << 1 | 1]); }
    S operator[](int i) { return tree[i + n]; }
    void set(int i, S x) {
        i += n;
        tree[i] = x;
        while (i >>= 1) {
            update(i);
        }
    }
    // [l,r)
    S query(int l, int r) {
        S sml = e(), smr = e();
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) sml = op(sml, tree[l++]);
            if (r & 1) smr = op(tree[--r], smr);
        }
        return op(sml, smr);
    }
};

using S = int;
S op(S a, S b) { return a + b; }
S e() { return 0; }

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;
    vector<ll> a(n), b(n); // bは座圧後何番目か?を表す(0-indexed)
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    // 極大な区間しか見なくて良い
    vector<int> rmx(n, -1);
    int q;
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        rmx[l] = max(rmx[l], r);
    }

    // 座圧
    auto z = a;
    sort(z.begin(), z.end());
    for (int i = 0; i < n; ++i) {
        b[i] = lower_bound(z.begin(), z.end(), a[i]) - z.begin();
    }

    segtree<S, op, e> seg(n);

    // 左端から区間を伸ばしていく
    int R = 0;
    for (int L = 0; L < n; ++L) {
        // 伸ばせるだけ伸ばす
        while (rmx[L] >= R) {
            // A[R]をpushする
            int i = b[R];
            seg.set(i, 1);
            R += 1;
        }
        if (L == R) {
            R += 1;
        } else {
            // A[L]をpopする
            int i = b[L];
            ll ad = seg.query(i + 1, n);
            res = max(res, ad * z[i]);
            seg.set(i, 0);
        }
    }

    cout << res << endl;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3640kb

input:

6
3 5 2 7 4 6
2
1 5
3 6

output:

9

result:

ok answer is '9'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3788kb

input:

1
100
1
1 1

output:

0

result:

ok answer is '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

20
451541695 690066663 673479208 448269517 560111835 982439295 929007403 955125568 735150915 829197546 256554877 435297385 348361716 763574893 202875223 881879899 590527232 256896900 31383620 400212120
5
4 8
4 17
11 13
19 20
17 18

output:

4480894680

result:

ok answer is '4480894680'

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3720kb

input:

100
310791482 148245051 114541081 918781914 681485137 656214017 226939378 970492592 431199764 162399115 490488808 3059986 487892489 611730708 952388887 418021477 917893766 587279310 363995315 342188612 72531000 156997725 896382592 359419647 144773021 872005978 496280920 65840663 56171913 273988049 6...

output:

21559988200

result:

wrong answer expected '23457460782', found '21559988200'