Submission #151887

#	Time	Username	Problem	Language	Result	Execution time	Memory
151887		EntityIT	역사적 조사 (JOI14_historical)	C++14	0 / 100	422 ms	27168 KiB

historic

#include<bits/stdc++.h>

using namespace std;

#define int ll

using ll = long long;

const int N = (int)1e5 + 5, BS = sqrt(N), NB = N / BS + 5;
int n, q, x[N], cnt[N], bIdOf[N], bBe[NB], bEn[NB], nB, prefCnt[NB][N];
ll mx[NB][NB];
vector<int> comp;

int32_t main() {
//    freopen("test.INP", "r", stdin);
    scanf("%lld %lld", &n, &q);
    comp.assign(n + 1, 0);
    for (int i = 1; i <= n; ++i) scanf("%lld", x + i), comp[i] = x[i];
    sort(comp.begin(), comp.end() ); comp.erase(unique(comp.begin(), comp.end() ), comp.end() );

    for (int i = 1; i <= n; ++i) x[i] = lower_bound(comp.begin(), comp.end(), x[i]) - comp.begin();

    for (int i = 1; i <= n; i += BS) {
        bBe[++nB] = i;
        bEn[nB] = min(n, bBe[nB] + BS - 1);
        for (int j = bBe[nB]; j <= bEn[nB]; ++j) bIdOf[j] = nB;
    }

    for (int i = 1; i <= nB; ++i) {
        ll ans = 0;
        memset(cnt, 0, sizeof cnt);
        for (int j = i; j <= nB; ++j) {
            for (int k = bBe[j]; k <= bEn[j]; ++k) {
                ++cnt[ x[k] ];
                ans = max(ans, (ll)comp[ x[k] ] * cnt[ x[k] ]);
            }
            mx[i][j] = ans;
        }

        for (int j = 1; j < (int)comp.size(); ++j) prefCnt[i][j] = prefCnt[i - 1][j];
        for (int j = bBe[i]; j <= bEn[i]; ++j) ++prefCnt[i][ x[j] ];
    }

    memset(cnt, 0, sizeof cnt);
    while (q --) {
        int l, r; scanf("%lld %lld", &l, &r);
        ll ans = 0;
        if (bIdOf[l] == bIdOf[r]) {
            for (int i = l; i <= r; ++i) {
                ans = max(ans, (ll)comp[ x[i] ] * (++cnt[ x[i] ]) );
            }
            for (int i = l; i <= r; ++i) --cnt[ x[i] ];
        }
        else {
            ans = mx[ bIdOf[l] + 1 ][ bIdOf[r] - 1 ];
            for (int i = l; i <= bEn[ bIdOf[l] ]; ++i) ans = max(ans, (ll)comp[ x[i] ] * ( (++cnt[ x[i] ]) + prefCnt[ bIdOf[r] - 1][ x[i] ] - prefCnt[ bIdOf[l] ][ x[i] ]) );
            for (int i = r; i >= bBe[ bIdOf[r] ]; --i) ans = max(ans, (ll)comp[ x[i] ] * ( (++cnt[ x[i] ]) + prefCnt[ bIdOf[r] - 1][ x[i] ] - prefCnt[ bIdOf[l] ][ x[i] ]) );

            for (int i = l; i <= bEn[ bIdOf[l] ]; ++i) --cnt[ x[i] ];
            for (int i = r; i >= bBe[ bIdOf[r] ]; --i) --cnt[ x[i] ];
        }

        printf("%I64d\n", ans);
    }

    return 0;
}

Compilation message (stderr)

historic.cpp: In function 'int32_t main()':
historic.cpp:63:30: warning: format '%d' expects argument of type 'int', but argument 2 has type 'll {aka long long int}' [-Wformat=]
         printf("%I64d\n", ans);
                              ^
historic.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %lld", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~
historic.cpp:18:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i = 1; i <= n; ++i) scanf("%lld", x + i), comp[i] = x[i];
                                  ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
historic.cpp:46:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int l, r; scanf("%lld %lld", &l, &r);
                   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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