Submission #469301

#	Time	Username	Problem	Language	Result	Execution time	Memory
469301		MohamedFaresNebili	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	475 ms	276272 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

using ll  = long long;
using ld  = long double;
using db  = double;
using ii  = pair<int, int>;
using pl  = pair<ll, ll>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vii = vector<ii>;
using vpl = vector<pl>;

#define mp make_pair
#define pb push_back
#define pp pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) (x).begin() , (x).end()

ld dist(ld x, ld y, ld a, ld b)    { return sqrt((x-a)*(x-a) + (y-b)*(y-b)); }
ll gcd(ll a , ll b){ return b ? gcd(b , a % b) : a ;}
ll lcm(ll a , ll b){ return (a * b) / gcd(a , b);}
ll fact(ll n) { return n > 1?(n * fact(n-1)):1;}

const ll MOD = 1000*1000*1000+7;
const long double EPS = 0.000000001;
const double PI = 3.14159265358979323846;
const long long INF = 1e18;
/// const int nx[4] = {0, 0, -1, 1}, ny[4] = {1, -1, 0, 0};
const int nx[8] = {2, 2, 1, -1, -2, -2, 1, -1};
const int ny[8] = {1, -1, 2, 2, -1, 1, -2, -2};


int st[4*200005];
void update(int v, int l, int r, int a, int b) {
    if(l==r) { st[v]+=b; return; }
    int mid=(l+r)/2;
    if(a<=mid) update(v*2, l, mid, a, b);
    else update(v*2+1, mid+1, r, a, b);
    st[v]=st[v*2]+st[v*2+1];
}
int query(int v, int l, int r, int lo, int hi) {
    if(l>hi||r<lo) return 0;
    if(l>=lo&&r<=hi) return st[v];
    return query(v*2, l, (l+r)/2, lo, hi)+query(v*2+1, (l+r)/2+1, r, lo, hi);
}

long long count_swaps(std::vector<int> s) {
    ll n=s.size(); ll res=0;
    priority_queue<pair<ii, int>>pq; 
	stack<int>lf[n], r[n];
    for(int i=0;i<n;i++) {
        update(1, 0, n-1, i, 1);
        if(s[i]>0) lf[s[i]].push(i);
        else r[-s[i]].push(i);
    }
    for(int l=1;l<=n/2;l++) {
		if((int)lf[l].size()==0) continue;
        ll a=lf[l].top(), b=r[l].top();
        if(a>b) swap(a, b);
        pq.push({{b, a}, l});
    }
    for(int l=n-1;l>=0;l--) {
		if(l&1) {
			ll j=pq.top().ss; ll u=lf[j].top(); lf[j].pop();
			ll k=query(1, 0, n-1, 0, u);
			res+=abs(l-k+1);
            update(1, 0, n-1, u, -1);
		}
		else {
			ll j=pq.top().ss; ll u=r[j].top(); r[j].pop(); 
			ll k=query(1, 0, n-1, 0, u);
			res+=abs(l-k+1);
            update(1, 0, n-1, u, -1);
			pq.pop();
			if((int)lf[j].size()) {
				ll a=lf[j].top(), b=r[j].top();
				if(a>b) swap(a, b);
				pq.push(mp(mp(b, a), j));
			}
		}
    }
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15