oj.uz

Submission #6948

# Submission time Handle Problem Language Result Execution time Memory
6948 2014-07-10T15:12:34 Z Qwaz 즐거운 채소 기르기 (JOI14_growing) C++
100 / 100
 268 ms 15424 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef pair < int, int > pii;
typedef long long ll;
const int MAX = 300020;
 
int n, data[MAX];
priority_queue < pii > fromL, fromR;
 
void input(){
    scanf("%d", &n);
 
    int i;
    for(i = 1; i<=n; i++){
        scanf("%d", &data[i]);
        fromL.push(pii(-data[i], -i));
        fromR.push(pii(-data[i], i));
    }
}
 
int left[MAX], right[MAX];
 
int get(int BIT[], int target){
    int ret = 0;
    while(target){
        ret += BIT[target];
        target -= target & -target;
    }
 
    return ret;
}
 
void update(int BIT[], int target, int val){
    while(target < MAX){
        BIT[target] += val;
        target += target & -target;
    }
}
 
ll res;
bool used[MAX];
 
void solve(){
    int i;
    for(i = 1; i<=n; i++){
        update(left, i, 1);
        update(right, n+1-i, 1);
    }
 
    for(i = 0; i<n; i++){
        int nowL = 0, nowR = 0;
        do {
            if(used[nowL]) fromL.pop();
            nowL = -fromL.top().second;
        } while(used[nowL]);
 
        do {
            if(used[nowR]) fromR.pop();
            nowR = fromR.top().second;
        } while(used[nowR]);
 
        int tL = min(get(left, nowL), get(right, n+1-nowL))-1;
        int tR = min(get(left, nowR), get(right, n+1-nowR))-1;
 
        int target;
        if(tL < tR){
            target = nowL;
            res += tL;
        } else {
            target = nowR;
            res += tR;
        }
 
        used[target] = 1;
        update(left, target, -1);
        update(right, n+1-target, -1);
    }
 
    printf("%lld\n", res);
}
 
int main(){
    input();
 
    solve();
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5048 KB Output is correct
2 Correct 0 ms 5048 KB Output is correct
3 Correct 0 ms 5048 KB Output is correct
4 Correct 0 ms 5048 KB Output is correct
5 Correct 0 ms 5048 KB Output is correct
6 Correct 0 ms 5048 KB Output is correct
7 Correct 0 ms 5048 KB Output is correct
8 Correct 0 ms 5048 KB Output is correct
9 Correct 0 ms 5048 KB Output is correct
10 Correct 0 ms 5048 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5048 KB Output is correct
2 Correct 0 ms 5048 KB Output is correct
3 Correct 0 ms 5048 KB Output is correct
4 Correct 0 ms 5048 KB Output is correct
5 Correct 0 ms 5048 KB Output is correct
6 Correct 0 ms 5048 KB Output is correct
7 Correct 0 ms 5048 KB Output is correct
8 Correct 0 ms 5048 KB Output is correct
9 Correct 0 ms 5048 KB Output is correct
10 Correct 0 ms 5048 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5048 KB Output is correct
2 Correct 0 ms 5048 KB Output is correct
3 Correct 0 ms 5048 KB Output is correct
4 Correct 0 ms 5048 KB Output is correct
5 Correct 4 ms 5196 KB Output is correct
6 Correct 0 ms 5196 KB Output is correct
7 Correct 0 ms 5196 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 4 ms 5196 KB Output is correct
10 Correct 0 ms 5196 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 6464 KB Output is correct
2 Correct 80 ms 7744 KB Output is correct
3 Correct 112 ms 10304 KB Output is correct
4 Correct 156 ms 10304 KB Output is correct
5 Correct 124 ms 10304 KB Output is correct
6 Correct 52 ms 7744 KB Output is correct
7 Correct 184 ms 15424 KB Output is correct
8 Correct 208 ms 15424 KB Output is correct
9 Correct 268 ms 15424 KB Output is correct
10 Correct 232 ms 15424 KB Output is correct