oj.uz

답안 #5995

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5995 2014-06-11T16:06:22 Z model_code 즐거운 채소 기르기 (JOI14_growing) C++
100 / 100
 324 ms 12220 KB 
#include <cstdio>
#include <cstdlib>
  #include <algorithm>

int N;
int segt[2250000];
void add(int id,int lf,int rg,int plc) {
    if(lf>plc||rg<plc) return;
    if(lf==rg&&lf==plc) {
        segt[id]=1;
        return;
    }
    int hf=(lf+rg)/2;
    add(id*2+1,lf,hf,plc);
    add(id*2+2,hf+1,rg,plc);
    segt[id]=segt[id*2+1]+segt[id*2+2];
}
int calc(int id,int lf,int rg,int callf,int calrg) {
    if(lf>calrg||rg<callf) return 0;
    if(callf<=lf&&calrg>=rg) return segt[id];
    int hf=(lf+rg)/2;
    return calc(id*2+1,lf,hf,callf,calrg)+calc(id*2+2,hf+1,rg,callf,calrg);
}
typedef struct {
    int vl;
    int plc;
}plts;
plts plt[300002];
/*
int cmp(const void *ka,const void *kb) {
    plts *a=(plts *)ka;
    plts *b=(plts *)kb;
    if(a->vl!=b->vl) return b->vl-a->vl;
    return a->plc-b->plc;
}*/


int cmp(const plts &a,const plts &b) {
    if(a.vl!=b.vl) return a.vl > b.vl;
    return a.plc < b.plc;
}

int getmin(int a,int b) {
    if(a>b) return b;
    return a;
}
int main() {
    scanf("%d",&N);
    for(int i=0;i<2250000;i++) segt[i]=0;
    for(int i=0;i<N;i++) {
        scanf("%d",&plt[i].vl);
        plt[i].plc=i+1;
    }
    //qsort(plt,N,sizeof(plts),cmp);
  std::sort(plt, plt+N, cmp);
    long long sol=0;
    int nw=0;
    while(nw<N) {
        int nvl=plt[nw].vl;
        int nwb=nw;
        while(nw<N) {
            if(plt[nw].vl!=nvl) break;
            sol+=getmin(calc(0,1,N,1,plt[nw].plc),calc(0,1,N,plt[nw].plc,N));
            nw++;
        }
        while(nwb<nw) {
            add(0,1,N,plt[nwb].plc);
            nwb++;
        }
    }
    printf("%lld\n",sol);
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12220 KB Output is correct
2 Correct 4 ms 12220 KB Output is correct
3 Correct 0 ms 12220 KB Output is correct
4 Correct 0 ms 12220 KB Output is correct
5 Correct 4 ms 12220 KB Output is correct
6 Correct 0 ms 12220 KB Output is correct
7 Correct 0 ms 12220 KB Output is correct
8 Correct 0 ms 12220 KB Output is correct
9 Correct 0 ms 12220 KB Output is correct
10 Correct 0 ms 12220 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12220 KB Output is correct
2 Correct 0 ms 12220 KB Output is correct
3 Correct 0 ms 12220 KB Output is correct
4 Correct 0 ms 12220 KB Output is correct
5 Correct 0 ms 12220 KB Output is correct
6 Correct 0 ms 12220 KB Output is correct
7 Correct 4 ms 12220 KB Output is correct
8 Correct 0 ms 12220 KB Output is correct
9 Correct 0 ms 12220 KB Output is correct
10 Correct 0 ms 12220 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12220 KB Output is correct
2 Correct 0 ms 12220 KB Output is correct
3 Correct 0 ms 12220 KB Output is correct
4 Correct 4 ms 12220 KB Output is correct
5 Correct 0 ms 12220 KB Output is correct
6 Correct 0 ms 12220 KB Output is correct
7 Correct 4 ms 12220 KB Output is correct
8 Correct 4 ms 12220 KB Output is correct
9 Correct 8 ms 12220 KB Output is correct
10 Correct 4 ms 12220 KB Output is correct

Subtask #4
55.0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 52 ms 12220 KB Output is correct
2 Correct 104 ms 12220 KB Output is correct
3 Correct 164 ms 12220 KB Output is correct
4 Correct 220 ms 12220 KB Output is correct
5 Correct 160 ms 12220 KB Output is correct
6 Correct 84 ms 12220 KB Output is correct
7 Correct 284 ms 12220 KB Output is correct
8 Correct 312 ms 12220 KB Output is correct
9 Correct 324 ms 12220 KB Output is correct
10 Correct 308 ms 12220 KB Output is correct