Submission #485845

#	Time	Username	Problem	Language	Result	Execution time	Memory
485845		qwerasdfzxcl	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	57 ms	11708 KiB

shoes

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

using namespace std;
typedef long long ll;
vector<int> pos[100100];
pair<int, int> a[100100];
struct Seg{
    int tree[400400], sz;
    void init(int n) {sz = n;}
    void update(int p, int x){for(tree[p+=sz]+=x;p>1;p>>=1) tree[p>>1]=tree[p]+tree[p^1];}
    int query(int l, int r){
        int ret = 0;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret += tree[l++];
            if (r&1) ret += tree[--r];
        }
        return ret;
    }
}tree;

inline int myabs(int x){
    if (x<0) return -x;
    return x;
}

long long count_swaps(std::vector<int> s) {
  	int n = s.size()/2;
    for (int i=n*2-1;i>=0;i--) if (s[i]<0) pos[-s[i]].push_back(i);
    ll ret = 0;
    vector<int> v1(s.size());
    int cnt = 1;
    for (int i=0;i<n*2;i++) if (s[i]>0){
        if (i<pos[s[i]].back()) ret++;
        else ret--;
        ret += myabs(i-pos[s[i]].back());
        a[cnt] = {i, pos[s[i]].back()};
        if (a[cnt].first>a[cnt].second) swap(a[cnt].first, a[cnt].second);
        v1[a[cnt].second] = a[cnt].first+1;

        pos[s[i]].pop_back();
        cnt++;
    }

    tree.init(n*2);
    for (int i=0;i<n*2;i++){
        if (v1[i]){
            tree.update(v1[i]-1, -1);
            ret += tree.query(0, v1[i]-1)*2;
        }
        else tree.update(i, 1);
    }
    return ret/2;
}

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