Submission #6948

#	Time	Username	Problem	Language	Result	Execution time	Memory
6948		Qwaz	즐거운 채소 기르기 (JOI14_growing)	C++98	100 / 100	268 ms	15424 KiB

growing

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55