답안 #81607 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
81607	2018-10-25T14:48:27 Z	luckyboy	Krov (COCI17_krov)	C++14	98 / 140	414 ms	7492 KB

krov

/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (long long i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (long long i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 500005
#define pii pair <long long,long long>
#define Task ""
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
long long n,a[maxn];
long long ans = 1ll*maxc*maxc;
struct BIT
{
    long long t[maxn];
    void Update(long long x,long long val)
    {
        while (x <= n)
        {
            t[x] += val;
            x += x & -x;
        }
    }
    long long Get(long long x)
    {
        long long res = 0;
        while (x)
        {
            res += t[x];
            x -= x & -x;
        }
        return res;
    }
}l1,l2,r1,r2;
vector <long long> L,R;
bool check(long long i,long long x)
{
    long long pos1 = upper_bound(L.begin(),L.end(),x - i) - L.begin(),
        pos2 = upper_bound(R.begin(),R.end(),x + i) - R.begin();
    pos1 = l1.Get(pos1);
    pos2 = r1.Get(pos2);
    return (pos1 + pos2) > (n - n / 2);
}
long long Calc(long long i,long long x)
{
    long long res = 0;
    long long il = upper_bound(L.begin(), L.end(), x - i) - L.begin();
	long long ir = upper_bound(R.begin(), R.end(), x + i) - R.begin();
	res += 1ll*(x - i) * l1.Get(il) - l2.Get(il);
	res += (l2.Get(n) - l2.Get(il)) - (1ll*(x - i) * (l1.Get(n) - l1.Get(il)));
	res += 1ll*(x + i) * r1.Get(ir) - r2.Get(ir);
	res += (r2.Get(n) - r2.Get(ir)) - (1ll*(x + i) * (r1.Get(n) - r1.Get(ir)));
	return res;
}
int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    read(n);
    FOR(i,1,n)
    {
        read(a[i]);
        L.pb(a[i] - i);
        R.pb(a[i] + i);
    }
    sort(L.begin(),L.end());
    sort(R.begin(),R.end());
    L.resize(unique(L.begin(),L.end()) - L.begin());
    R.resize(unique(R.begin(),R.end()) - R.begin());
    FOR(i,1,n)
    {
        long long pos = upper_bound(R.begin(),R.end(),a[i] + i) - R.begin();
        r1.Update(pos,1);
        r2.Update(pos,a[i] + i);
    }
    FOR(i,1,n)
    {
        long long pos1 = upper_bound(L.begin(),L.end(),a[i] - i) - L.begin(),
            pos2 = upper_bound(R.begin(),R.end(),a[i] + i) - R.begin();
        l1.Update(pos1,1);
        l2.Update(pos1,a[i] - i);
        r1.Update(pos2,-1);
        r2.Update(pos2,-a[i] - i);
        long long l = max(i,n-i+1),r = maxc + maxn * 2;
        while (r - l > 1)
        {
            long long mid = (l+r) >> 1;
            if (check(i,mid)) r = mid;
            else l = mid;
        }
        ans = min(ans,Calc(i,r));
        ans = min(ans,Calc(i,l));
    }
    write(ans);
    return 0;
}

Subtask #1
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	508 KB	Output is correct

Subtask #2
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	552 KB	Output is correct
2	Correct	5 ms	576 KB	Output is correct

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	660 KB	Output is correct
2	Correct	6 ms	748 KB	Output is correct

Subtask #4
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	7 ms	796 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	820 KB	Output is correct
2	Correct	10 ms	840 KB	Output is correct

Subtask #6
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	18 ms	1112 KB	Output is correct
2	Correct	16 ms	1112 KB	Output is correct
3	Correct	9 ms	1112 KB	Output is correct

Subtask #7
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	96 ms	2624 KB	Output is correct
2	Correct	75 ms	2624 KB	Output is correct
3	Correct	95 ms	2944 KB	Output is correct
4	Correct	125 ms	3240 KB	Output is correct

Subtask #8
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	159 ms	3984 KB	Output is correct
2	Correct	189 ms	4296 KB	Output is correct
3	Correct	122 ms	4296 KB	Output is correct
4	Incorrect	119 ms	4296 KB	Output isn't correct

Subtask #9
0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	263 ms	4544 KB	Output is correct
2	Incorrect	237 ms	6028 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #10
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	347 ms	7492 KB	Output is correct
2	Correct	357 ms	7492 KB	Output is correct
3	Correct	323 ms	7492 KB	Output is correct
4	Correct	414 ms	7492 KB	Output is correct
5	Correct	104 ms	7492 KB	Output is correct

답안 #81607

Compilation message