Submission #207310

#	Time	Username	Problem	Language	Result	Execution time	Memory
207310		balbit	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	176 ms	140152 KiB

shoes

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

#define ll long long
#define pb push_back
#define SZ(x) (int)((x).size())
#define ALL(x) x.begin(),x.end()

#define pii pair<int, int>
#define f first
#define s second

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = ", _do(__VA_ARGS__)
template<typename T> void _do(T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif // BALBIT

const int maxn = 2e5+5;

queue<pii> tp[maxn];

ll s[maxn];
ll QU(int e) { // Number of things leq
    ll re = 0;
    for (e++; e>0; e-=e&-e) re += s[e];
    return re;
}
void MO(int e, int v) {
    for (e++;e<maxn;e+=e&-e)s[e]+=v;
}
inline int sgn(int x){return x>0?1:-1;}
ll count_swaps(vector<int> s) {
    int n = s.size();
    for (int i = 0; i<n; i++) {
        MO(i,1);
    }
    ll re = 0;
    for (int i = 0; i<n; i++) {
        int x = abs(s[i]);
        int ig = sgn(s[i]);
        if (tp[x].size()==0 || sgn(tp[x].front().s) == ig) {
            tp[x].push({i,s[i]});
        }else{
            re += QU(i-1) - QU(tp[x].front().f);
            if (ig == -1) ++re;
            MO(i,-1);
            MO(tp[x].front().f,1);
            tp[x].pop();
        }
    }
//    for (int i = 0; i<n*2; i++) {
//        cerr<<s[i]<<' ';
//    }
//    cerr<<endl;
    return re;
}

#ifdef BALBIT
signed main(){
    IOS();
    int n; cin>>n;
    vector<int> x(n*2);
    for (int i = 0; i<n*2; i++) cin>>x[i];
    cout<<count_swaps(x)<<endl;
}
#endif

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