Submission #368400

#	Time	Username	Problem	Language	Result	Execution time	Memory
368400		xuannhiminh	Krov (COCI17_krov)	C++14	140 / 140	399 ms	6132 KiB

krov

#include <iostream>
#include <vector>
#include <algorithm>
#define base 1000000007
template <typename T>void read(T& x)
{
    x = 0; T f = 1;
    char ch = getchar_unlocked();
    while (!isdigit(ch)) f = ch == '-' ? - f : f, ch = getchar_unlocked();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar_unlocked();
    x *= f;
}

template<typename T> void write(T n) 
{ 
	bool neg = 0; 

	if (n < 0) 
		n *= -1, neg = 1; 

	char snum[20]; 
	int i = 0; 
	do
	{ 
		snum[i++] = n % 10 + '0'; 
		n /= 10; 
	} 

	while (n); 
	--i; 

	if (neg) 
		putchar_unlocked('-'); 

	while (i >= 0) 
		putchar_unlocked(snum[i--]); 

	putchar_unlocked('\n'); 
} 


using namespace std;
int n,a[100005];
long long kq = 1ll*base*base;
struct BIT
{
    long long t[100005];
    void capnhat(int x,int val)
    {
        while (x <= n)
        {
            t[x] += val;
            x += x & -x;
        }
    }
    long long lay(int x)
    {
        long long res = 0;
        while (x)
        {
            res += t[x];
            x -= x & -x;
        }
        return res;
    }
}l1,l2,r1,r2;
vector <int> L,R;
bool check(int i,int x)
{
    int vt1 = upper_bound(L.begin(),L.end(),x - i) - L.begin(),
        vt2 = upper_bound(R.begin(),R.end(),x + i) - R.begin();
    vt1 = l1.lay(vt1);
    vt2 = r1.lay(vt2);
    return (vt1 + vt2) >= (n - n / 2);
}
long long tinh(int i,int x)
{
    long long res = 0;
    int il = upper_bound(L.begin(), L.end(), x - i) - L.begin();
	int ir = upper_bound(R.begin(), R.end(), x + i) - R.begin();
	res += 1ll*(x - i) * l1.lay(il) - l2.lay(il);
	res += (l2.lay(n) - l2.lay(il)) - (1ll*(x - i) * (l1.lay(n) - l1.lay(il)));
	res += 1ll*(x + i) * r1.lay(ir) - r2.lay(ir);
	res += (r2.lay(n) - r2.lay(ir)) - (1ll*(x + i) * (r1.lay(n) - r1.lay(ir)));
	return res;
}
main()
{

    read(n);
    for (int i = 1; i <= n; ++i)
    {
        read(a[i]);
        L.emplace_back(a[i] - i);
        R.emplace_back(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 (int i = 1; i <= n; ++i)
    {
        int vt = upper_bound(R.begin(),R.end(),a[i] + i) - R.begin();
        r1.capnhat(vt,1);
        r2.capnhat(vt,a[i] + i);
    }
     for (int i = 1; i <= n; ++i)
    {
        int vt1 = upper_bound(L.begin(),L.end(),a[i] - i) - L.begin(),
            vt2 = upper_bound(R.begin(),R.end(),a[i] + i) - R.begin();
        l1.capnhat(vt1,1);
        l2.capnhat(vt1,a[i] - i);
        r1.capnhat(vt2,-1);
        r2.capnhat(vt2,-a[i] - i);
        int l = max(i,n-i+1) - 1,r = base + 100005 * 2;
        while (r - l > 1)
        {
            int mid = (l+r) >> 1;
            if (check(i,mid)) r = mid;
            else l = mid;
        }
        kq = min(kq,tinh(i,r));
    }
    write(kq);
}

Compilation message (stderr)

krov.cpp:87:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main()
      |      ^

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 14 / 14
• Subtask 5: 14 / 14
• Subtask 6: 14 / 14
• Subtask 7: 14 / 14
• Subtask 8: 14 / 14
• Subtask 9: 14 / 14
• Subtask 10: 14 / 14