Submission #1192781

#TimeUsernameProblemLanguageResultExecution timeMemory
1192781vnedu즐거운 채소 기르기 (JOI14_growing)C++17
30 / 100
12 ms3212 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; template<class T> bool maximize(T &a, const T &b){ return (a < b ? a = b, 1 : 0); } template<class T> bool minimize(T &a, const T &b){ return (a > b ? a = b, 1 : 0); } #define fi first #define se second #define pb push_back #define ii pair<int, int> #define all(x) x.begin(), x.end() #define TASK "nonsense" /// end of template /// const int N = 3e5 + 10; int n,a[N],bit[N]; vector<int> nen; void add(int x, int val) { x=n-x+1; while(x<=n) { bit[x]+=val; x+=x&-x; } } int get(int x) { x=n-x+1; int ans=0; while(x>=1) { ans+=bit[x]; x-=x&-x; } return ans; } ll p[N],s[N]; void solve() { cin>>n; for(int i=1;i<=n;++i) cin>>a[i],nen.pb(a[i]); sort(all(nen)); nen.erase(unique(all(nen)),nen.end()); for(int i=1;i<=n;++i) { int x=lower_bound(all(nen),a[i])-nen.begin()+1; p[i]=p[i-1]+get(x+1); add(x,1); } memset(bit,0,sizeof(bit)); for(int i=n;i>=1;--i) { int x=lower_bound(all(nen),a[i])-nen.begin()+1; s[i]=s[i+1]+get(x+1); add(x,1); } ll ans=LLONG_MAX; for(int i=0;i<=n;++i) minimize(ans,p[i]+s[i+1]); cout<<ans; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); // freopen(TASK".inp","r",stdin); // freopen(TASK".out","w",stdout); int testcase=1; // cin>>testcase; while (testcase--) solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...