oj.uz

Submission #11204

# Submission time Handle Problem Language Result Execution time Memory
11204 2014-11-18T15:21:07 Z dohyun0324 역사적 조사 (JOI14_historical) C++
100 / 100
 1848 ms 79336 KB 
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
int s2,f,w,r,p,cnt,x,y,n,m,k,pos[100010],arr[100010],ch[100010];
long long dap,big;
struct data{
    int x,y;
    bool operator<(const data&r)const{
        if(x==r.x) return y<r.y;
        return x<r.x;
    }
}imsi[100010];
long long b[3010][3010];
vector<int>a[100010];
int main()
{
    int i,j,s;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){scanf("%d",&arr[i]); imsi[i].x=arr[i]; imsi[i].y=i;}
    sort(imsi+1,imsi+n+1);
    for(i=1;i<=n;i++)
    {
        if(imsi[i].x!=imsi[i-1].x) cnt++;
        pos[cnt]=imsi[i].x; arr[imsi[i].y]=cnt; a[cnt].push_back(imsi[i].y);
    }
    k=sqrt(n);
    if(n>=100) k=50;
    for(i=1;;i++){
        w=i-1; big=0; memset(ch,0,sizeof ch);
        if(k*(i-1)+1>n) break;
        for(j=k*(i-1)+1;j<=n;j++){
            ch[arr[j]]++;
            big=max(big,(long long)ch[arr[j]]*(long long)pos[arr[j]]);
            if(j%k==0){w++; b[i][w]=big;}
        }
        if(n%k!=0){w++; b[i][w]=big;}
    }
    p=i;
    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&x,&y);
        f=(x-1)/k+2; r=(y-1)/k;
        dap=b[f][r];
        if(f>r){
            for(j=x;j<=y;j++){
                s=upper_bound(a[arr[j]].begin(),a[arr[j]].end(),y)-lower_bound(a[arr[j]].begin(),a[arr[j]].end(),x);
                dap=max(dap,(long long)s*(long long)pos[arr[j]]);
            }
            printf("%lld\n",dap);
            continue;
        }
        for(j=x;j<=(f-1)*k;j++)
        {
            s=upper_bound(a[arr[j]].begin(),a[arr[j]].end(),y)-lower_bound(a[arr[j]].begin(),a[arr[j]].end(),x);
            dap=max(dap,(long long)s*(long long)pos[arr[j]]);
        }
        for(j=r*k+1;j<=y;j++)
        {
            s=upper_bound(a[arr[j]].begin(),a[arr[j]].end(),y)-lower_bound(a[arr[j]].begin(),a[arr[j]].end(),x);
            dap=max(dap,(long long)s*(long long)pos[arr[j]]);
        }
        printf("%lld\n",dap);
    }
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 76300 KB Output is correct
2 Correct 4 ms 76300 KB Output is correct
3 Correct 8 ms 76300 KB Output is correct
4 Correct 8 ms 76300 KB Output is correct
5 Correct 20 ms 76300 KB Output is correct
6 Correct 32 ms 76300 KB Output is correct
7 Correct 32 ms 76300 KB Output is correct
8 Correct 44 ms 76300 KB Output is correct
9 Correct 40 ms 76300 KB Output is correct
10 Correct 28 ms 76300 KB Output is correct
11 Correct 20 ms 76300 KB Output is correct
12 Correct 24 ms 76300 KB Output is correct
13 Correct 24 ms 76300 KB Output is correct
14 Correct 28 ms 76300 KB Output is correct
15 Correct 28 ms 76300 KB Output is correct
16 Correct 36 ms 76300 KB Output is correct
17 Correct 40 ms 76300 KB Output is correct
18 Correct 24 ms 76300 KB Output is correct
19 Correct 24 ms 76300 KB Output is correct
20 Correct 20 ms 76300 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 76300 KB Output is correct
2 Correct 0 ms 76300 KB Output is correct
3 Correct 0 ms 76300 KB Output is correct
4 Correct 0 ms 76300 KB Output is correct
5 Correct 4 ms 76300 KB Output is correct
6 Correct 4 ms 76300 KB Output is correct
7 Correct 4 ms 76300 KB Output is correct
8 Correct 20 ms 76300 KB Output is correct
9 Correct 72 ms 76432 KB Output is correct
10 Correct 256 ms 76816 KB Output is correct
11 Correct 1524 ms 76876 KB Output is correct
12 Correct 884 ms 76828 KB Output is correct
13 Correct 952 ms 76960 KB Output is correct
14 Correct 1132 ms 77620 KB Output is correct
15 Correct 1032 ms 78016 KB Output is correct
16 Correct 1052 ms 79336 KB Output is correct
17 Correct 972 ms 76700 KB Output is correct
18 Correct 1156 ms 76696 KB Output is correct
19 Correct 920 ms 79336 KB Output is correct
20 Correct 876 ms 79336 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 76300 KB Output is correct
2 Correct 160 ms 76300 KB Output is correct
3 Correct 244 ms 76432 KB Output is correct
4 Correct 348 ms 76696 KB Output is correct
5 Correct 460 ms 76828 KB Output is correct
6 Correct 680 ms 76696 KB Output is correct
7 Correct 1024 ms 76696 KB Output is correct
8 Correct 1368 ms 76724 KB Output is correct
9 Correct 1608 ms 76844 KB Output is correct
10 Correct 1432 ms 77072 KB Output is correct
11 Correct 1832 ms 76952 KB Output is correct
12 Correct 1848 ms 76828 KB Output is correct
13 Correct 1548 ms 76960 KB Output is correct
14 Correct 1312 ms 77356 KB Output is correct
15 Correct 1368 ms 78016 KB Output is correct
16 Correct 1412 ms 77620 KB Output is correct
17 Correct 1360 ms 77620 KB Output is correct
18 Correct 1428 ms 77488 KB Output is correct
19 Correct 1388 ms 77356 KB Output is correct
20 Correct 1368 ms 77356 KB Output is correct
21 Correct 1408 ms 77356 KB Output is correct
22 Correct 1396 ms 77224 KB Output is correct
23 Correct 1392 ms 77224 KB Output is correct
24 Correct 1392 ms 77224 KB Output is correct
25 Correct 1380 ms 77072 KB Output is correct