oj.uz

Submission #11202

# Submission time Handle Problem Language Result Execution time Memory
11202 2014-11-18T15:06:30 Z dohyun0324 역사적 조사 (JOI14_historical) C++
40 / 100
 4000 ms 9804 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[400][400];
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);
    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 6768 KB Output is correct
2 Correct 0 ms 6768 KB Output is correct
3 Correct 0 ms 6768 KB Output is correct
4 Correct 0 ms 6768 KB Output is correct
5 Correct 0 ms 6768 KB Output is correct
6 Correct 0 ms 6768 KB Output is correct
7 Correct 0 ms 6768 KB Output is correct
8 Correct 4 ms 6768 KB Output is correct
9 Correct 0 ms 6768 KB Output is correct
10 Correct 0 ms 6768 KB Output is correct
11 Correct 0 ms 6768 KB Output is correct
12 Correct 0 ms 6768 KB Output is correct
13 Correct 0 ms 6768 KB Output is correct
14 Correct 0 ms 6768 KB Output is correct
15 Correct 0 ms 6768 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6768 KB Output is correct
2 Correct 0 ms 6768 KB Output is correct
3 Correct 0 ms 6768 KB Output is correct
4 Correct 0 ms 6768 KB Output is correct
5 Correct 4 ms 6768 KB Output is correct
6 Correct 4 ms 6768 KB Output is correct
7 Correct 8 ms 6768 KB Output is correct
8 Correct 20 ms 6768 KB Output is correct
9 Correct 24 ms 6900 KB Output is correct
10 Correct 92 ms 7284 KB Output is correct
11 Correct 1200 ms 7344 KB Output is correct
12 Correct 180 ms 7296 KB Output is correct
13 Correct 788 ms 7428 KB Output is correct
14 Correct 872 ms 8088 KB Output is correct
15 Correct 272 ms 8484 KB Output is correct
16 Correct 824 ms 9804 KB Output is correct
17 Correct 932 ms 7168 KB Output is correct
18 Correct 1996 ms 7164 KB Output is correct
19 Correct 500 ms 9804 KB Output is correct
20 Correct 248 ms 9804 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 6768 KB Output is correct
2 Correct 340 ms 6768 KB Output is correct
3 Correct 544 ms 6900 KB Output is correct
4 Correct 704 ms 7164 KB Output is correct
5 Correct 1132 ms 7296 KB Output is correct
6 Correct 1816 ms 7164 KB Output is correct
7 Correct 3012 ms 7164 KB Output is correct
8 Correct 3928 ms 7192 KB Output is correct
9 Correct 3584 ms 7312 KB Output is correct
10 Correct 3196 ms 7540 KB Output is correct
11 Execution timed out 4000 ms 7420 KB Program timed out
12 Halted 0 ms 0 KB -