oj.uz

Submission #368400

# Submission time Handle Problem Language Result Execution time Memory
368400 2021-02-20T02:58:44 Z xuannhiminh Krov (COCI17_krov) C++14
140 / 140
 399 ms 6132 KB 
#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

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 3 ms 364 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 364 KB Output is correct
2 Correct 5 ms 364 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 492 KB Output is correct
2 Correct 6 ms 492 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 492 KB Output is correct
2 Correct 7 ms 492 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 620 KB Output is correct
2 Correct 13 ms 620 KB Output is correct
3 Correct 8 ms 492 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1644 KB Output is correct
2 Correct 67 ms 1412 KB Output is correct
3 Correct 110 ms 1900 KB Output is correct
4 Correct 128 ms 1900 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 2408 KB Output is correct
2 Correct 179 ms 2664 KB Output is correct
3 Correct 116 ms 2664 KB Output is correct
4 Correct 118 ms 2616 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 3136 KB Output is correct
2 Correct 254 ms 4448 KB Output is correct
3 Correct 162 ms 2352 KB Output is correct
4 Correct 350 ms 3936 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 367 ms 6132 KB Output is correct
2 Correct 355 ms 5792 KB Output is correct
3 Correct 338 ms 4192 KB Output is correct
4 Correct 399 ms 5088 KB Output is correct
5 Correct 91 ms 1772 KB Output is correct