oj.uz

Submission #43223

# Submission time Handle Problem Language Result Execution time Memory
43223 2018-03-11T01:16:16 Z smu201111192 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 398 ms 223480 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 202488 KB Output is correct
2 Correct 193 ms 202488 KB Output is correct
3 Correct 193 ms 202536 KB Output is correct
4 Correct 188 ms 202536 KB Output is correct
5 Correct 190 ms 202680 KB Output is correct
6 Correct 188 ms 202680 KB Output is correct
7 Correct 190 ms 202680 KB Output is correct
8 Correct 192 ms 202712 KB Output is correct
9 Correct 189 ms 202716 KB Output is correct
10 Correct 194 ms 202716 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 202864 KB Output is correct
2 Correct 190 ms 202864 KB Output is correct
3 Correct 199 ms 202864 KB Output is correct
4 Correct 187 ms 202864 KB Output is correct
5 Correct 186 ms 202864 KB Output is correct
6 Correct 188 ms 202864 KB Output is correct
7 Correct 189 ms 202864 KB Output is correct
8 Correct 186 ms 202864 KB Output is correct
9 Correct 185 ms 202864 KB Output is correct
10 Correct 191 ms 202864 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 202864 KB Output is correct
2 Correct 213 ms 202932 KB Output is correct
3 Correct 211 ms 202932 KB Output is correct
4 Correct 210 ms 203088 KB Output is correct
5 Correct 213 ms 203208 KB Output is correct
6 Correct 212 ms 203208 KB Output is correct
7 Correct 212 ms 203208 KB Output is correct
8 Correct 212 ms 203208 KB Output is correct
9 Correct 215 ms 203336 KB Output is correct
10 Correct 217 ms 203368 KB Output is correct

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 204304 KB Output is correct
2 Correct 263 ms 205828 KB Output is correct
3 Correct 318 ms 207464 KB Output is correct
4 Correct 356 ms 210008 KB Output is correct
5 Correct 274 ms 211956 KB Output is correct
6 Correct 239 ms 211956 KB Output is correct
7 Correct 285 ms 215644 KB Output is correct
8 Correct 356 ms 217676 KB Output is correct
9 Correct 371 ms 221000 KB Output is correct
10 Correct 398 ms 223480 KB Output is correct