oj.uz

Submission #11191

# Submission time Handle Problem Language Result Execution time Memory
11191 2014-11-18T14:38:23 Z dohyun0324 역사적 조사 (JOI14_historical) C++
40 / 100
 4000 ms 11760 KB 
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
long long s2,f,w,dap,r,p,cnt,x,y,n,m,k,pos[100010],arr[100010],ch[100010],big;
struct data{
    long long 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<long long>a[100010];
int main()
{
    long long i,j,s;
    scanf("%lld %lld",&n,&m);
    for(i=1;i<=n;i++){scanf("%lld",&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,ch[arr[j]]*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("%lld %lld",&x,&y);
        f=(x-1)/k+2; r=(y-1)/k;
        dap=b[f][r];
        for(j=x;j<=(f-1)*k;j++)
        {
            if(j>y) break;
            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,s*pos[arr[j]]);
        }
        for(j=r*k+1;j<=y;j++)
        {
            if(j<x) break;
            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,s*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 8724 KB Output is correct
2 Correct 0 ms 8724 KB Output is correct
3 Correct 0 ms 8724 KB Output is correct
4 Correct 0 ms 8724 KB Output is correct
5 Correct 0 ms 8724 KB Output is correct
6 Correct 0 ms 8724 KB Output is correct
7 Correct 0 ms 8724 KB Output is correct
8 Correct 4 ms 8724 KB Output is correct
9 Correct 0 ms 8724 KB Output is correct
10 Correct 0 ms 8724 KB Output is correct
11 Correct 0 ms 8724 KB Output is correct
12 Correct 0 ms 8724 KB Output is correct
13 Correct 0 ms 8724 KB Output is correct
14 Correct 0 ms 8724 KB Output is correct
15 Correct 0 ms 8724 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8724 KB Output is correct
2 Correct 0 ms 8724 KB Output is correct
3 Correct 4 ms 8724 KB Output is correct
4 Correct 0 ms 8724 KB Output is correct
5 Correct 0 ms 8724 KB Output is correct
6 Correct 4 ms 8724 KB Output is correct
7 Correct 12 ms 8724 KB Output is correct
8 Correct 24 ms 8856 KB Output is correct
9 Correct 48 ms 8988 KB Output is correct
10 Correct 128 ms 9752 KB Output is correct
11 Correct 1376 ms 9856 KB Output is correct
12 Correct 304 ms 9796 KB Output is correct
13 Correct 888 ms 9912 KB Output is correct
14 Correct 1032 ms 10308 KB Output is correct
15 Correct 480 ms 10704 KB Output is correct
16 Correct 1036 ms 11760 KB Output is correct
17 Correct 976 ms 9684 KB Output is correct
18 Correct 1884 ms 9548 KB Output is correct
19 Correct 560 ms 11760 KB Output is correct
20 Correct 376 ms 11760 KB Output is correct

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 8724 KB Output is correct
2 Correct 332 ms 8856 KB Output is correct
3 Correct 508 ms 9120 KB Output is correct
4 Correct 640 ms 9252 KB Output is correct
5 Correct 888 ms 9384 KB Output is correct
6 Correct 1680 ms 9384 KB Output is correct
7 Correct 2960 ms 9516 KB Output is correct
8 Correct 3552 ms 9636 KB Output is correct
9 Correct 3380 ms 9708 KB Output is correct
10 Correct 2888 ms 10264 KB Output is correct
11 Execution timed out 4000 ms 9888 KB Program timed out
12 Halted 0 ms 0 KB -