제출 #965105

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
965105		weakweakweak	역사적 조사 (JOI14_historical)	C++17	100 / 100	316 ms	25044 KiB

historic

//回滾莫隊 裸題
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;

#define fs first
#define sc second

int n, q, a[510000], cnt[510000] = {0};
long long nowans, ans[510000];
vector <int> b;
int B;
vector <pair<pii,int>> qs[510000];

void add (int x) {
    cnt[x]++;
    nowans = max(nowans, b[x] * 1LL * cnt[x]);
}

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> q;
    B = sqrt((n + q + 1) / 2);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        b.push_back(a[i]);
    }
    sort (b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();

    for (int i = 1; i <= q; i++) {
        pii p;
        cin >> p.fs >> p.sc;
        int lb = p.fs / B, rb = p.sc / B;
        if (lb == rb) { // 特判塊太小
            for (int j = p.fs; j <= p.sc; j++) cnt[a[j]] = 0;
            nowans = 0;
            for (int j = p.fs; j <= p.sc; j++) add(a[j]);
            ans[i] = nowans;
            continue;
        }
        qs[p.fs / B] . push_back({p, i}); 
    }

    for (int i = 1 / B; i <= n / B; i++) {
        sort(qs[i].begin(), qs[i].end(), [](pair<pii,int>a, pair<pii,int>b){return a.fs.sc < b.fs.sc;} );
        int RB = min(i * B + B, n), R = RB - 1;
        nowans = 0;
        memset(cnt, 0, sizeof(cnt));
        for (auto qq : qs[i]) {
            while (R < qq.fs.sc) {
                R++;
                add(a[R]);
            }
            long long oldans = nowans;
            vector <pii> old;
            for (int j = RB - 1; j >= qq.fs.fs; j--) old.push_back({a[j], cnt[a[j]]});
            for (int j = RB - 1; j >= qq.fs.fs; j--) add(a[j]);
            ans[qq.sc] = nowans;
            nowans = oldans;
            for (pii p : old) cnt[p.fs] = p.sc;
        }
    }

    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
return 0;}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60