Submission #899517

#	Time	Username	Problem	Language	Result	Execution time	Memory
899517		SuPythony	Arranging Shoes (IOI19_shoes)	C++17	30 / 100	1083 ms	37396 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX=1e5+7;
vector<ll> seg(4*MAX);

void build(vector<ll> s, int v, int tl, int tr) {
    if (tl==tr) {
        seg[v]=s[tl];
    } else {
        int tm=(tl+tr)/2;
        build(s, v*2, tl, tm);
        build(s, v*2+1, tm+1, tr);
        seg[v]=seg[v*2]+seg[v*2+1];
    }
}

ll sum(int v, int tl, int tr, int l, int r) {
    if (l>r) return 0;
    if (l==tl&&r==tr) return seg[v];
    int tm=(tl+tr)/2;
    return sum(v*2, tl, tm, l, min(r, tm))+sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int v, int tl, int tr, int pos) {
    if (tl==tr) {
        seg[v]=0;
    } else {
        int tm=(tl+tr)/2;
        if (pos<=tm) {
            update(v*2, tl, tm, pos);
        } else {
            update(v*2+1, tm+1, tr, pos);
        }
        seg[v]=seg[v*2]+seg[v*2+1];
    }
}

ll count_swaps(vector<int> S) {
    int n=S.size();
    vector<ll> s(n, 1);
    build(s, 1, 0, n-1);
    unordered_map<int,pair<vector<int>,int>> pos;
    for (int i=0; i<n; i++) {
        pos[S[i]].first.push_back(i);
        pos[S[i]].second=0;
    }
    ll ans=0;
    for (int i=0; i<n; i+=1) {
        if (s[i]==1) {
            int j=pos[-S[i]].first[pos[-S[i]].second];
            ans+=sum(1, 0, n-1, i+1, j-1);
            if (S[i]>0) ans+=1;
            s[i]=0;
            s[j]=0;
            update(1, 0, n-1, i);
            update(1, 0, n-1, j);
            pos[-S[i]].second++;
        }
    }
    return ans;
}

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