Greedy Game

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef long long ll;
const ll MN = 1e5+100;
const ll N = 1<<17;
pair<ll, ll> t[MN];
pair<ll, ll> b[MN];
ll st[2*N];
ll sisu[2*N];
ll getMin(ll k, ll l, ll r, ll x, ll y) {
    if(l > y || r < x) return 1e9;
    if(l >= x && r <= y) {
	return st[k];
    }
    ll mid = (l+r)/2;
    ll q = getMin(k*2, l, mid, x, y);
    ll w = getMin(k*2+1, mid+1, r, x, y);
    return min(q, w) + sisu[k];
}
ll add(ll k, ll l, ll r, ll x, ll y, ll v) {
    if(l > y || r < x) return st[k];
    if(l >= x && r <= y) {
	sisu[k] += v;
	st[k] += v;
	return st[k];
    }
    ll mid = (l+r)/2;
    ll q = add(k*2, l, mid, x, y, v);
    ll w = add(k*2+1, mid+1, r, x, y, v);
    return st[k] = q + w;
}
ll st2[2*N];
ll getSum(int a, int b) {
    a += N; b += N;
    ll sum = 0;
    for(; a <= b; a/=2, b/=2) {
	if(a&1) sum += st2[a++];
	if(~b&1) sum += st2[b--];
    }
    return sum;
}
void addValue(int a, int v) {
    a += N;
    for(; a; a/=2) {
	st2[a] += v;
    }
}
ll pos[MN];
int main() {
    ll n;
    cin>>n;
    for(ll i = 0; i< n; ++i) {
	cin>>t[i].F;
	t[i].S = i;
    }
    for(int i = 0; i < n; ++i) {
	cin>>b[i].F;
	b[i].S = i;
    }
    sort(t, t+n);
    for(ll i = 0; i < n; ++i) {
	pos[t[i].S] = i;
    }
    for(int i = 0; i < 2*N; ++i) {
	st[i] = 1e9;
    }
    sort(b, b+n);
    long long ans = 0;
    for(ll i = n-1; i >= 0; --i) {
	ll x = pos[b[i].S];
	//cout<<x<<' '<<b[i].F<<' '<<b[i].S<<'\n';
	if(x == n-1) continue;
	int q = getSum(x+1, N-1);
	if(getMin(1, 0, N-1,0, x-1) != 0 && (q)*2 < (n-x-1)) {
	    add(1, 0, N-1, 0, x-1, -1);
	    int jalj = (n-x-1) - (q)*2-1;
	    //cout<<"hei "<<b[i].F<<' '<<q<<' '<<jalj<<'\n';
	    ll q = getMin(1, 0, N-1, x, x);
	    add(1, 0, N-1, x, x, -q+jalj);
	    addValue(x, 1);
	    ans += b[i].F;
	}
    }
    cout<<ans<<'\n';
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: WRONG ANSWER

Test 5

Verdict: WRONG ANSWER

Test 6

Verdict: WRONG ANSWER

Test 7

Verdict: WRONG ANSWER

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: WRONG ANSWER

Test 10

Verdict: WRONG ANSWER

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: WRONG ANSWER

Test 13

Verdict: WRONG ANSWER

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER

Test 16

Verdict: WRONG ANSWER

Test 17

Verdict: WRONG ANSWER

Test 18

Verdict: WRONG ANSWER

Test 19

Verdict: WRONG ANSWER

Test 20

Verdict: WRONG ANSWER

Test 21

Verdict: WRONG ANSWER

Test 22

Verdict: WRONG ANSWER

Test 23

Verdict: WRONG ANSWER

Test 24

Verdict: WRONG ANSWER

Test 25

Verdict: WRONG ANSWER

Test 26

Verdict: WRONG ANSWER

Test 27

Verdict: WRONG ANSWER

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: WRONG ANSWER