oj.uz

Submission #42354

# Submission time Handle Problem Language Result Execution time Memory
42354 2018-02-26T11:47:46 Z dqhungdl 즐거운 채소 기르기 (JOI14_growing) C++14
30 / 100
 30 ms 3448 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t n,a[300005],f1[300005],f2[300005],tree[300005];
ii b[300005];

void Update(int64_t idx)
{
    while(idx>0)
    {
        tree[idx]++;
        idx-=idx&-idx;
    }
}

int64_t Query(int64_t idx)
{
    int64_t rs=0;
    while(idx<=n)
    {
        rs+=tree[idx];
        idx+=idx&-idx;
    }
    return rs;
}

int main()
{
    cin>>n;
    for(int64_t i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=ii(a[i],i);
    }
    sort(b+1,b+n+1);
    a[b[1].second]=1;
    int Count=1;
    for(int64_t i=2;i<=n;i++)
        if(b[i].first>b[i-1].first)
            a[b[i].second]=++Count;
        else
            a[b[i].second]=Count;
    for(int64_t i=1;i<=n;i++)
    {
        f1[i]=f1[i-1]+Query(a[i]+1);
        Update(a[i]);
    }
    for(int64_t i=1;i<=n;i++)
        tree[i]=0;
    for(int64_t i=n;i>=1;i--)
    {
        f2[i]=f2[i+1]+Query(a[i]+1);
        Update(a[i]);
    }
    int64_t res=1e12;
    for(int64_t i=1;i<=n;i++)
        res=min(res,min(f1[i]+f2[i+1],f1[i-1]+f2[i]));
    cout<<res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Correct 1 ms 488 KB Output is correct
7 Correct 2 ms 488 KB Output is correct
8 Correct 1 ms 544 KB Output is correct
9 Correct 1 ms 560 KB Output is correct
10 Correct 2 ms 560 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 3448 KB Output isn't correct
2 Halted 0 ms 0 KB -