oj.uz

Submission #11203

# Submission time Handle Problem Language Result Execution time Memory
11203 2014-11-18T15:18:33 Z dohyun0324 역사적 조사 (JOI14_historical) C++
15 / 100
 4000 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>=5000) k=3000;
    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 0 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 0 ms 76300 KB Output is correct
2 Correct 0 ms 76300 KB Output is correct
3 Correct 4 ms 76300 KB Output is correct
4 Correct 12 ms 76300 KB Output is correct
5 Correct 16 ms 76300 KB Output is correct
6 Correct 636 ms 76300 KB Output is correct
7 Correct 612 ms 76300 KB Output is correct
8 Correct 700 ms 76300 KB Output is correct
9 Correct 620 ms 76300 KB Output is correct
10 Correct 384 ms 76300 KB Output is correct
11 Correct 364 ms 76300 KB Output is correct
12 Correct 432 ms 76300 KB Output is correct
13 Correct 428 ms 76300 KB Output is correct
14 Correct 464 ms 76300 KB Output is correct
15 Correct 444 ms 76300 KB Output is correct
16 Correct 656 ms 76300 KB Output is correct
17 Correct 496 ms 76300 KB Output is correct
18 Correct 432 ms 76300 KB Output is correct
19 Correct 360 ms 76300 KB Output is correct
20 Correct 328 ms 76300 KB Output is correct

Subtask #3
0.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 4 ms 76300 KB Output is correct
4 Correct 4 ms 76300 KB Output is correct
5 Correct 0 ms 76300 KB Output is correct
6 Correct 4 ms 76300 KB Output is correct
7 Correct 0 ms 76300 KB Output is correct
8 Correct 4 ms 76300 KB Output is correct
9 Correct 20 ms 76432 KB Output is correct
10 Correct 44 ms 76816 KB Output is correct
11 Correct 1024 ms 76876 KB Output is correct
12 Correct 64 ms 76828 KB Output is correct
13 Correct 920 ms 76960 KB Output is correct
14 Correct 640 ms 77620 KB Output is correct
15 Correct 132 ms 78016 KB Output is correct
16 Execution timed out 4000 ms 79336 KB Program timed out
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 2008 ms 76300 KB Output is correct
2 Execution timed out 4000 ms 76300 KB Program timed out
3 Halted 0 ms 0 KB -