oj.uz

Submission #259040

# Submission time Handle Problem Language Result Execution time Memory
259040 2020-08-07T05:00:14 Z 강태규(#5095) 역사적 조사 (JOI14_historical) C++17
0 / 100
 210 ms 1980 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;
int cnt[100001];

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

void sub(int i) {
    int x = X[i];
    pq2.push(1ll * 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];
    }
    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 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.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 #3
0 / 25.0

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

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 1980 KB Output is correct
2 Runtime error 10 ms 1184 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -