제출 #1247857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247857		tvgk	역사적 조사 (JOI14_historical)	C++20	100 / 100	120 ms	13636 KiB

historic

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
#define iii pair<ii, int>
const long mxN = 1e5 + 7, nB = 317;

int n, q, a[mxN];
ll val[mxN], cnt[mxN], ans[mxN];
map<int, int> m;
vector<iii> querry[mxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n >> q;
    int num = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];

        if (!m[a[i]])
        {
            m[a[i]] = ++num;
            val[num] = a[i];
        }
        a[i] = m[a[i]];
    }

    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;

        if (u / nB == v / nB)
        {
            for (int j = u; j <= v; j++)
            {
                cnt[a[j]]++;
                ans[i] = max(ans[i], cnt[a[j]] * val[a[j]]);
            }
            for (int j = u; j <= v; j++)
                cnt[a[j]] = 0;
        }
        else
            querry[u / nB].push_back({{v, u}, i});
    }

    for (int i = 0; i <= n / nB; i++)
    {
        sort(querry[i].begin(), querry[i].end());

        int r = (i + 1) * nB;
        ll mx = 0;
        for (iii j : querry[i])
        {
            while (r <= j.fi.fi)
            {
                cnt[a[r]]++;
                mx = max(mx, cnt[a[r]] * val[a[r]]);
                r++;
            }

            ans[j.se] = mx;
            for (int u = j.fi.se; u < (i + 1) * nB; u++)
            {
                cnt[a[u]]++;
                ans[j.se] = max(ans[j.se], cnt[a[u]] * val[a[u]]);
            }
            for (int u = j.fi.se; u < (i + 1) * nB; u++)
                cnt[a[u]]--;
        }

        for (int j = (i + 1) * nB; j <= n; j++)
            cnt[a[j]] = 0;
    }

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

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