oj.uz

Submission #766137

# Submission time Handle Problem Language Result Execution time Memory
766137 2023-06-25T10:34:19 Z bachhoangxuan 즐거운 채소 기르기 (JOI14_growing) C++17
100 / 100
 62 ms 13512 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 300005
#define int long long
#define pii pair<int,int>
int bit[maxn],n,cnt=0;
vector<pii> x;
int query(int a){
    int res=0;
    for(int i=a;i>=1;i-=(i&(-i))) res+=bit[i];
    return res;
}
void update(int a){
    for(int i=a;i<=n;i+=(i&(-i))) bit[i]++;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> n;
    for(int i=1;i<=n;i++){
        int a;cin >> a;
        x.push_back({a,i});
    }
    sort(x.begin(),x.end());
    int ans=0;
    while(!x.empty()){
        pii p=x.back();x.pop_back();
        int sum=query(p.second);sum=min(sum,cnt-sum);
        vector<int> add={p.second};
        while(!x.empty() && x.back().first==p.first){
            int a=query(x.back().second);
            sum+=min(a,cnt-a);add.push_back(x.back().second);
            x.pop_back();
        }
        //cout << cnt << ' ' << sum << '\n';
        ans+=sum;cnt+=(int)add.size();
        for(int v:add) update(v);
    }
    cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 2000 KB Output is correct
2 Correct 23 ms 3880 KB Output is correct
3 Correct 30 ms 5708 KB Output is correct
4 Correct 41 ms 7344 KB Output is correct
5 Correct 26 ms 7000 KB Output is correct
6 Correct 21 ms 3760 KB Output is correct
7 Correct 49 ms 9780 KB Output is correct
8 Correct 61 ms 11256 KB Output is correct
9 Correct 62 ms 13512 KB Output is correct
10 Correct 58 ms 11452 KB Output is correct