Submission #43223

#	Time	Username	Problem	Language	Result	Execution time	Memory
43223		smu201111192	즐거운 채소 기르기 (JOI14_growing)	C++14	100 / 100	398 ms	223480 KiB

growing

#include <iostream>
#include <cstdio>
#include <cassert>
#include <bitset>
#include <string>
#include <sstream>
#include <algorithm>
#include <set>
#include <numeric>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
#include <queue>
#include <numeric>
#include <iomanip>
#define ll long long
using namespace std;
const int MAXN = 300005;
vector<int> vx;
deque<int> dq[MAXN];
int arr[MAXN],n;
int tree[MAXN];
void update(int pos,int val){
    if(pos <= 0)return;
    for(;pos<MAXN;pos+=pos&-pos) tree[pos] += val;
}
int go(int pos){
    if(pos<=0) return 0;
    int ret = 0;
    for(;pos>0;pos-=pos&-pos) ret += tree[pos];
    return ret;
}
int query(int l,int r){
    if(l > r) return 0;
    return go(r) - go(l-1);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> arr[i];
    for(int i = 1; i <= n; i++) vx.push_back(arr[i]);
    sort(vx.begin(),vx.end());
    vx.erase(unique(vx.begin(),vx.end()),vx.end());
    for(int i = 1; i <= n; i++){
        arr[i] = lower_bound(vx.begin(),vx.end(),arr[i]) - vx.begin() + 1;
        dq[arr[i]].push_back(i);
        update(i,1);
    }
    long long ans = 0;
    for(int i = 1; i <= n; i++){
        while(dq[i].size()){
            int front = dq[i].front();
            int back = dq[i].back();
            int fcnt = query(1 , front-1);
            int bcnt = query(back+1 , n);
            if(fcnt <= bcnt){
                ans += fcnt;
                update(front,-1);
                dq[i].pop_front();
            }
            else{
                ans += bcnt;
                update(back,-1);
                dq[i].pop_back();
            }
        }
    }
    cout<<ans;
    
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55