Submission #143779

#	Time	Username	Problem	Language	Result	Execution time	Memory
143779		dongwon0427	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	105 ms	19308 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int n;
vector<int> L[200005], R[200005];
vector<pii> P;

int fenwick[200005];
void updt(int idx,int v) {
    idx++;
    while(idx <= n) {
        fenwick[idx] += v;
        idx += idx & (-idx);
    }
}
int sum(int idx) {
    idx++;
    int ret = 0;
    while(idx) {
        ret += fenwick[idx];
        idx -= idx & (-idx);
    }
    return ret;
}

ll count_swaps(std::vector<int> s) {
	n = s.size();
	for(int i=0;i<n;i++) {
        if(s[i] < 0) {
            L[-s[i]].push_back(i);
        } else {
            R[s[i]].push_back(i);
        }
	}
	ll ret = 0;
	for(int i=0;i<=n;i++) {
        for(int j=0;j<L[i].size();j++) {
            if(R[i][j] < L[i][j]) ret++;
            P.push_back(pii(min(L[i][j],R[i][j]), max(L[i][j],R[i][j])));
        }
	}
	sort(P.begin(),P.end());

	for(int i=0;i<n;i++) {
        updt(i,1);
	}
	for(pii p : P) {
        //cout<<p.first<<' '<<p.second<<'\n';
        ret += (ll)sum(p.second-1) - sum(p.first);
        updt(p.second, -1);
	}
	return ret;
}

Compilation message (stderr)

shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<L[i].size();j++) {
                     ~^~~~~~~~~~~~

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