oj.uz

Submission #259043

# Submission time Handle Problem Language Result Execution time Memory
259043 2020-08-07T05:03:28 Z 강태규(#5095) 역사적 조사 (JOI14_historical) C++17
10 / 100
 4000 ms 51456 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long llong;
typedef pair<int, int> pii;

const int B = 400;
int n, q;
int X[100001];
pair<pii, int> Q[100001];
priority_queue<llong> pq1, pq2;
vector<int> cp;
int cnt[100001];

void add(int i) {
    int x = X[i];
    pq1.push(1ll * cp[x] * ++cnt[x]);
}

void sub(int i) {
    int x = X[i];
    pq2.push(1ll * cp[x] * cnt[x]--);
    while (!pq1.empty() && pq1.top() == pq2.top()) {
        pq1.pop();
        pq2.pop();
    }
}

llong ans[100001];
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> q;
    pq1.push(0);
    for (int i = 1; i <= n; ++i) {
        cin >> X[i];
        cp.push_back(X[i]);
    }
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for (int i = 1; i <= n; ++i) {
        X[i] = lower_bound(cp.begin(), cp.end(), X[i]) - cp.begin();
    }
    for (int i = 1; i <= q; ++i) {
        cin >> Q[i].first.first >> Q[i].first.second;
        Q[i].second = i;
    }
    sort(Q + 1, Q + (q + 1), [&](pair<pii, int> a, pair<pii, int> b) {
        int ga = a.first.first / B, gb = b.first.first / B;
        if (ga != gb) return ga < gb;
        return a.first.second < b.first.second;
    });
    int s = 1, e = 0;
    for (int i = 1; i <= q; ++i) {
        auto [x, y] = Q[i].first;
        while (e < y) add(++e);
        while (x < s) add(--s);
        while (y < e) sub(e--);
        while (s < x) sub(s++);
        ans[Q[i].second] = pq1.top();
    }
    for (int i = 1; i <= q; ++i) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 10 ms 1020 KB Output is correct
4 Correct 24 ms 1404 KB Output is correct
5 Correct 60 ms 1404 KB Output is correct
6 Correct 99 ms 1456 KB Output is correct
7 Correct 93 ms 1568 KB Output is correct
8 Correct 99 ms 1456 KB Output is correct
9 Correct 102 ms 1456 KB Output is correct
10 Correct 77 ms 3728 KB Output is correct
11 Correct 88 ms 3736 KB Output is correct
12 Correct 90 ms 2580 KB Output is correct
13 Correct 80 ms 3876 KB Output is correct
14 Correct 86 ms 3864 KB Output is correct
15 Correct 91 ms 2328 KB Output is correct
16 Correct 111 ms 1508 KB Output is correct
17 Correct 94 ms 1456 KB Output is correct
18 Correct 92 ms 3736 KB Output is correct
19 Correct 98 ms 3732 KB Output is correct
20 Correct 70 ms 3736 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 3 ms 640 KB Output is correct
8 Correct 5 ms 896 KB Output is correct
9 Correct 11 ms 1224 KB Output is correct
10 Runtime error 12 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 1748 KB Output is correct
2 Correct 565 ms 4384 KB Output is correct
3 Correct 871 ms 15608 KB Output is correct
4 Correct 1497 ms 30544 KB Output is correct
5 Correct 1831 ms 51456 KB Output is correct
6 Correct 2717 ms 27956 KB Output is correct
7 Correct 3539 ms 9408 KB Output is correct
8 Execution timed out 4035 ms 5936 KB Time limit exceeded
9 Halted 0 ms 0 KB -