oj.uz

Submission #151887

# Submission time Handle Problem Language Result Execution time Memory
151887 2019-09-05T09:58:13 Z EntityIT 역사적 조사 (JOI14_historical) C++14
0 / 100
 422 ms 27168 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1272 KB Output is correct
2 Incorrect 3 ms 1144 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 5 ms 1272 KB Output is correct
4 Incorrect 7 ms 1400 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1144 KB Output is correct
3 Correct 3 ms 1144 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 4 ms 1272 KB Output is correct
6 Correct 5 ms 1272 KB Output is correct
7 Correct 7 ms 1656 KB Output is correct
8 Incorrect 11 ms 2808 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2552 KB Output is correct
2 Correct 72 ms 4088 KB Output is correct
3 Correct 147 ms 8644 KB Output is correct
4 Correct 285 ms 18412 KB Output is correct
5 Correct 422 ms 27168 KB Output is correct
6 Incorrect 342 ms 16736 KB Output isn't correct
7 Halted 0 ms 0 KB -