oj.uz

Submission #13002

# Submission time Handle Problem Language Result Execution time Memory
13002 2015-01-24T06:51:18 Z gs14004 역사적 조사 (JOI14_historical) C++
5 / 100
 308 ms 5592 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int B = 300;

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

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);
    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;
        for (int i=p; ; i++) {
            mv = max(mv,1ll * v[a[i]] * range_count(p,q,a[i]));
            if(i % B == 0) break;
        }
        mv = max(mv,buck[p/B+1][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=1; 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=1; 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 + 1 ~ j * B
    for (int i=1; i<=n; i+=B) {
        long long cnt[100005] = {};
        long long max = 0;
        for (int j=i; j<=n; j++) {
            cnt[a[j]] += v[j];
            if(cnt[a[j]] < max) max = cnt[a[j]];
            if(j % B == 0){
                buck[i/B][j/B] = max;
            }
        }
    }
    while (q--) {
        query();
    }
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5592 KB Output is correct
2 Correct 4 ms 5588 KB Output is correct
3 Incorrect 4 ms 5588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5588 KB Output is correct
2 Correct 0 ms 5592 KB Output is correct
3 Correct 0 ms 5592 KB Output is correct
4 Correct 0 ms 5592 KB Output is correct
5 Correct 0 ms 5592 KB Output is correct
6 Correct 0 ms 5588 KB Output is correct
7 Incorrect 8 ms 5588 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 308 ms 5588 KB Output isn't correct
2 Halted 0 ms 0 KB -