Submission #485974

#	Time	Username	Problem	Language	Result	Execution time	Memory
485974		qwerasdfzxcl	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	59 ms	8824 KiB

shoes

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

using namespace std;
typedef long long ll;
int v1[200200];
vector<int> pos[100100];
struct Seg{
    int tree[200200], sz;
    void update(int p, int x){while(p<=sz){tree[p]+=x; p+=p&-p;}}
    int query(int r){
        int ret = 0;
        while(r){
            ret += tree[r];
            r ^= r&-r;
        }
        return ret;
    }
}tree;

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;
    for (int i=0;i<n*2;i++) if (s[i]>0){
        if (i<pos[s[i]].back()){
            ret += pos[s[i]].back()-i+1;
            v1[pos[s[i]].back()] = i+1;
        }
        else{
            ret += i-pos[s[i]].back()-1;
            v1[i] = pos[s[i]].back()+1;
        }

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

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

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