Submission #742330

#	Time	Username	Problem	Language	Result	Execution time	Memory
742330		haydendoo	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	194 ms	141324 KiB

shoes

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

typedef pair<int,int> pi;

const int N=2e5+10;

int fw[N], fw2[N];
void update(int x, int y, int v) { //inclusive
    ++x; ++y;
    for (int tx=x; tx < N; tx += tx&(-tx)) fw[tx] += v, fw2[tx] -= v*(x-1);
    for (int ty=y+1; ty < N; ty += ty&(-ty)) fw[ty] -= v, fw2[ty] += v*y; 
}
int sum (int x) {
    ++x;
    int res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res;
}
int range_sum(int x, int y) { //inclusive
    return sum(y)-sum(x-1);
}

long long count_swaps(vector<int> s) {
    int n=s.size();
	deque<int> dq[n/2+1], dq2[n/2+1];
    for(int i=0; i<n; ++i) {
        if(s[i]<0) dq[-s[i]].push_back(i+1);
        else dq2[s[i]].push_back(i+1);
    }
    for(int i=0; i<=n; ++i) {
        update(i+1,i+1,i+1);
    }
    long long ans=0;
    vector<pair<int,int>> pairs;
    for(int i=1; i<=n/2; ++i) {
        for(int j=0; j<dq[i].size(); ++j) {
            if(dq[i][j]>dq2[i][j]) {
                ++ans;
                swap(dq[i][j], dq2[i][j]);
            }
            pairs.emplace_back(dq[i][j], dq2[i][j]);
        }
    }
    sort(pairs.begin(), pairs.end());
    long long cnt=0;
    for(auto it: pairs) {
        int l=it.first, r=it.second;
        ans += range_sum(r,r) + range_sum(l,l) - (cnt*2+1) - (cnt*2+2); //<< '\n';
        ++cnt;
        update(0,l,1); update(0,r,1);
    }
    return ans;
}

// int main() {
//     cout << count_swaps({2,1,-1,-2});
// }

/*
dq[1] = [2]
dq[2] = [1]
dq2[1] = [3]
dq2[2] = [4]
*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         for(int j=0; j<dq[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