Submission #776986

#	Time	Username	Problem	Language	Result	Execution time	Memory
776986		Trisanu_Das	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	207 ms	274024 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
 
const int N = 2e5+10;
 
int n, fenwick[N];
queue<int> shoes_l[N], shoes_r[N];
 
void upd(int pos, int val) {
    for(int i = pos; i <= n; i+= i&-i) {
        fenwick[i]+= val;
    }
}
 
int get(int pos) {
    int val = 0;
    for(int i = pos; i > 0; i-= i&-i) {
        val+= fenwick[i];
    }
    return val;
}
 
int count_swaps(vector<int32_t> s) {
    n = s.size();
    int ans = 0;
    for(int i = 1; i <= n; i++) {
        int temp = s[i-1];
 
        if(temp < 0) {
            temp *= -1;
            if(shoes_r[temp].size()){
                int pos = shoes_r[temp].front(); shoes_r[temp].pop();ans+= get(i) - get(pos-1);upd(pos,1);
            }
            else {
                shoes_l[temp].push(i); upd(i,1);
            }
        }
        else {
            if(shoes_l[temp].size()){
                int pos = shoes_l[temp].front(); shoes_l[temp].pop();ans+= get(i)-get(pos);upd(pos,1);
            }
            else {
                shoes_r[temp].push(i); upd(i,1);
            }
        }
    }
    return ans;
}

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