oj.uz

Submission #11201

# Submission time Handle Problem Language Result Execution time Memory
11201 2014-11-18T15:04:00 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 4 ms 6768 KB Output is correct
7 Correct 0 ms 6768 KB Output is correct
8 Correct 0 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 4 ms 6768 KB Output is correct
4 Correct 8 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 40 ms 6768 KB Output is correct
8 Correct 64 ms 6768 KB Output is correct
9 Correct 52 ms 6768 KB Output is correct
10 Correct 24 ms 6768 KB Output is correct
11 Correct 24 ms 6768 KB Output is correct
12 Correct 36 ms 6768 KB Output is correct
13 Correct 32 ms 6768 KB Output is correct
14 Correct 32 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 44 ms 6768 KB Output is correct
18 Correct 32 ms 6768 KB Output is correct
19 Correct 20 ms 6768 KB Output is correct
20 Correct 20 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 72 ms 7284 KB Output is correct
11 Correct 1220 ms 7344 KB Output is correct
12 Correct 188 ms 7296 KB Output is correct
13 Correct 768 ms 7428 KB Output is correct
14 Correct 836 ms 8088 KB Output is correct
15 Correct 320 ms 8484 KB Output is correct
16 Correct 776 ms 9804 KB Output is correct
17 Correct 956 ms 7168 KB Output is correct
18 Correct 1964 ms 7164 KB Output is correct
19 Correct 508 ms 9804 KB Output is correct
20 Correct 260 ms 9804 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 6768 KB Output is correct
2 Correct 352 ms 6768 KB Output is correct
3 Correct 492 ms 6900 KB Output is correct
4 Correct 740 ms 7164 KB Output is correct
5 Correct 1056 ms 7296 KB Output is correct
6 Correct 1828 ms 7164 KB Output is correct
7 Correct 2836 ms 7164 KB Output is correct
8 Correct 3996 ms 7192 KB Output is correct
9 Correct 3656 ms 7312 KB Output is correct
10 Correct 3044 ms 7540 KB Output is correct
11 Execution timed out 4000 ms 7420 KB Program timed out
12 Halted 0 ms 0 KB -