oj.uz

Submission #13007

# Submission time Handle Problem Language Result Execution time Memory
13007 2015-01-24T07:28:18 Z gs14004 역사적 조사 (JOI14_historical) C++
100 / 100
 2460 ms 12028 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int B = 150;

int n,q;
int a[100005];
long long buck[701][701];

vector<int> v;
vector<int> show[100005];

inline int range_count(int p, int q, int o){
    return (int)(upper_bound(show[o].begin(),show[o].end(),q) - lower_bound(show[o].begin(),show[o].end(),p));
}

void query(){
    int p,q;
    scanf("%d %d",&p,&q);
    p--;
    q--;
    if(p/B == q/B){
        long long mv = 0;
        for (int i=p; i<=q; i++) {
            mv = max(mv,1ll * v[a[i]] * range_count(p,q,a[i]));
        }
        printf("%lld\n",mv);
        return;
    }
    else{
        long long mv = 0;
        int i;
        for (i=p; i%B != 0; i++) {
            mv = max(mv,1ll * v[a[i]] * range_count(p,q,a[i]));
        }
        mv = max(mv,buck[i/B][q/B]);
        for (int i=q/B*B+1; i<=q; i++) {
            mv = max(mv,1ll * v[a[i]] * range_count(p,q,a[i]));
        }
        printf("%lld\n",mv);
    }
}

int main(){
    scanf("%d %d",&n,&q);
    for (int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        v.push_back(a[i]);
    }
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for (int i=0; i<n; i++) {
        a[i] = (int)(lower_bound(v.begin(),v.end(),a[i]) - v.begin());
        show[a[i]].push_back(i);
    }
    // buck[i][j] = i * B ~ j * B
    for (int i=0; i<n; i+=B) {
        long long cnt[100005] = {};
        long long maxv = 0;
        for (int j=i; j<n; j++) {
            cnt[a[j]] += v[a[j]];
            maxv = max(maxv,cnt[a[j]]);
            if(j % B== 0){
                buck[i/B][j/B] = maxv;
            }
        }
    }
    while (q--) {
        query();
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8476 KB Output is correct
3 Correct 0 ms 8476 KB Output is correct
4 Correct 0 ms 8472 KB Output is correct
5 Correct 0 ms 8472 KB Output is correct
6 Correct 0 ms 8476 KB Output is correct
7 Correct 0 ms 8476 KB Output is correct
8 Correct 0 ms 8476 KB Output is correct
9 Correct 0 ms 8476 KB Output is correct
10 Correct 0 ms 8472 KB Output is correct
11 Correct 0 ms 8476 KB Output is correct
12 Correct 0 ms 8472 KB Output is correct
13 Correct 0 ms 8476 KB Output is correct
14 Correct 0 ms 8476 KB Output is correct
15 Correct 0 ms 8472 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8476 KB Output is correct
2 Correct 0 ms 8472 KB Output is correct
3 Correct 8 ms 8476 KB Output is correct
4 Correct 12 ms 8472 KB Output is correct
5 Correct 32 ms 8476 KB Output is correct
6 Correct 68 ms 8472 KB Output is correct
7 Correct 60 ms 8476 KB Output is correct
8 Correct 72 ms 8476 KB Output is correct
9 Correct 76 ms 8472 KB Output is correct
10 Correct 40 ms 8476 KB Output is correct
11 Correct 36 ms 8472 KB Output is correct
12 Correct 36 ms 8476 KB Output is correct
13 Correct 44 ms 8476 KB Output is correct
14 Correct 40 ms 8472 KB Output is correct
15 Correct 44 ms 8476 KB Output is correct
16 Correct 80 ms 8476 KB Output is correct
17 Correct 60 ms 8476 KB Output is correct
18 Correct 44 ms 8472 KB Output is correct
19 Correct 36 ms 8472 KB Output is correct
20 Correct 32 ms 8480 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8472 KB Output is correct
2 Correct 0 ms 8476 KB Output is correct
3 Correct 0 ms 8476 KB Output is correct
4 Correct 0 ms 8476 KB Output is correct
5 Correct 0 ms 8476 KB Output is correct
6 Correct 4 ms 8476 KB Output is correct
7 Correct 0 ms 8476 KB Output is correct
8 Correct 16 ms 8604 KB Output is correct
9 Correct 28 ms 8872 KB Output is correct
10 Correct 60 ms 9420 KB Output is correct
11 Correct 1092 ms 9512 KB Output is correct
12 Correct 176 ms 9520 KB Output is correct
13 Correct 444 ms 9652 KB Output is correct
14 Correct 636 ms 10308 KB Output is correct
15 Correct 380 ms 10704 KB Output is correct
16 Correct 440 ms 12028 KB Output is correct
17 Correct 440 ms 9520 KB Output is correct
18 Correct 784 ms 9524 KB Output is correct
19 Correct 320 ms 12028 KB Output is correct
20 Correct 208 ms 12024 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8476 KB Output is correct
2 Correct 300 ms 8740 KB Output is correct
3 Correct 356 ms 8872 KB Output is correct
4 Correct 436 ms 9128 KB Output is correct
5 Correct 556 ms 9260 KB Output is correct
6 Correct 912 ms 9128 KB Output is correct
7 Correct 1532 ms 9384 KB Output is correct
8 Correct 1864 ms 9392 KB Output is correct
9 Correct 1792 ms 9464 KB Output is correct
10 Correct 1392 ms 10012 KB Output is correct
11 Correct 2072 ms 9752 KB Output is correct
12 Correct 2460 ms 9520 KB Output is correct
13 Correct 1720 ms 9648 KB Output is correct
14 Correct 1276 ms 10048 KB Output is correct
15 Correct 1140 ms 10704 KB Output is correct
16 Correct 1208 ms 10316 KB Output is correct
17 Correct 1240 ms 10312 KB Output is correct
18 Correct 1284 ms 10180 KB Output is correct
19 Correct 1292 ms 10044 KB Output is correct
20 Correct 1352 ms 10044 KB Output is correct
21 Correct 1344 ms 10044 KB Output is correct
22 Correct 1364 ms 9912 KB Output is correct
23 Correct 1396 ms 9916 KB Output is correct
24 Correct 1396 ms 9912 KB Output is correct
25 Correct 1368 ms 10016 KB Output is correct