Submission #397755

#	Time	Username	Problem	Language	Result	Execution time	Memory
397755		ivan24	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	733 ms	47400 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

class SegmentTree {
private:
    ll n;
    vi st,data;
    ll left(ll x){ return (x << 1); }
    ll right(ll x){ return ((x << 1) + 1); }
    void build (ll i, ll l, ll r){
        if (l == r){
            st[i] = data[l];
        }else{
            ll m = (l+r)/2;
            build (left(i),l,m);
            build (right(i),m+1,r);
        }
    }
    ll query (ll i, ll l, ll r, ll ql, ll qr){
        if (qr >= r && l >= ql){
            return st[i];
        }else if (ql > r || l > qr){
            return 0;
        }else{
            ll m = (l+r)/2;
            ll ans = 0;
            ans += query(left(i),l,m,ql,qr);
            ans += query(right(i),m+1,r,ql,qr);
            return ans;
        }
    }
    void update (ll i, ll l, ll r, ll idx, ll dx){
        if (r >= idx && idx >= l){
            if (r == l){
                st[i] += dx;
            }else{
                ll m = (l+r)/2;
                update(left(i),l,m,idx,dx);
                update(right(i),m+1,r,idx,dx);
                st[i] = st[left(i)] + st[right(i)];
            }
        }
    }
public:
    SegmentTree (const vi& _data): data(_data){
        n = data.size();
        st.resize(4*n);
    }
    ll query (ll l, ll r){
        return query(1,0,n-1,l,r);
    }
    void update (ll idx, ll dx){
        update(1,0,n-1,idx,dx);
    }
};


map<ll,set<ll> > byVals;

long long count_swaps(vector<int> s) {
    ll n;
    n = s.size(); n /= 2;
    ll ans = 0;
    SegmentTree st(vi(2*n,0));
    set<ll> available;

    for (ll i = 0; 2*n > i; i++){
        if (byVals.find(s[i]) == byVals.end()) byVals[s[i]] = set<ll>() ;
        byVals[s[i]].insert(i);
        available.insert(i);
    }

    for (ll i = 0; n > i; i++){
        ll ptr = *available.begin();
        ll ptr2 = *byVals[-s[ptr]].begin();

        ll modptr = st.query(0,ptr)+ptr;
        ll modptr2 = st.query(0,ptr2)+ptr2;

        ans += modptr2-1;
        if (s[ptr] > 0) ans++;

        //cout << ptr << ' ' << ptr2 << ' ' << modptr << ' ' << modptr2 << endl;

        available.erase(ptr);
        available.erase(ptr2);
        byVals[s[ptr]].erase(ptr);
        byVals[s[ptr2]].erase(ptr2);
        st.update(ptr,-1);
        st.update(ptr2,-1);
    }
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:86:12: warning: unused variable 'modptr' [-Wunused-variable]
   86 |         ll modptr = st.query(0,ptr)+ptr;
      |            ^~~~~~

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