oj.uz

Submission #42358

# Submission time Handle Problem Language Result Execution time Memory
42358 2018-02-26T13:32:03 Z dqhungdl 즐거운 채소 기르기 (JOI14_growing) C++14
100 / 100
 117 ms 8560 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t n,res=0,treeL[300005],treeR[300005];
ii a[300005];

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

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

void UpdateR(int64_t idx)
{
    while(idx<=n)
    {
        treeR[idx]++;
        idx+=idx&-idx;
    }
}

int64_t QueryR(int64_t idx)
{
    int64_t rs=0;
    while(idx>0)
    {
        rs+=treeR[idx];
        idx-=idx&-idx;
    }
    return rs;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n;
    for(int64_t i=1; i<=n; i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    int64_t tmp=1,L=0,R=n+1;
    for(int64_t i=2; i<=n; i++)
        if(a[i].first!=a[i-1].first)
        {
            int64_t id=-1,l=tmp,r=i-1;
            while(l<=r)
            {
                int64_t posl=a[l].second+QueryL(a[l].second)-QueryR(a[l].second);
                int64_t posr=a[r].second+QueryL(a[r].second)-QueryR(a[r].second);
                int64_t moveL=posl-L-1;
                int64_t moveR=R-posr-1;
                res+=min(moveL,moveR);
                if(moveL<moveR)
                {
                    UpdateL(a[l].second);
                    l++;
                    L++;
                }
                else
                {
                    UpdateR(a[r].second);
                    r--;
                    R--;
                }
            }
            tmp=i;
        }
    cout<<res;
}

Compilation message

growing.cpp: In function 'int main()':
growing.cpp:63:21: warning: unused variable 'id' [-Wunused-variable]
             int64_t id=-1,l=tmp,r=i-1;
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 356 KB Output is correct
3 Correct 2 ms 412 KB Output is correct
4 Correct 2 ms 428 KB Output is correct
5 Correct 1 ms 476 KB Output is correct
6 Correct 1 ms 532 KB Output is correct
7 Correct 1 ms 548 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 1 ms 548 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
15.0 / 15.0

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

Subtask #4
55.0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2028 KB Output is correct
2 Correct 32 ms 3052 KB Output is correct
3 Correct 46 ms 4156 KB Output is correct
4 Correct 63 ms 5356 KB Output is correct
5 Correct 43 ms 5356 KB Output is correct
6 Correct 34 ms 5356 KB Output is correct
7 Correct 79 ms 7660 KB Output is correct
8 Correct 102 ms 7856 KB Output is correct
9 Correct 117 ms 7856 KB Output is correct
10 Correct 93 ms 8560 KB Output is correct