Submission #887197

#	Time	Username	Problem	Language	Result	Execution time	Memory
887197		theghostking	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	72 ms	20948 KiB

shoes

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

vector<int> tree;

int nc;

int query(int a, int b){
    a += nc;
    b += nc;
    int s = 0;
    while (a <= b){
        if (a%2){
            s += tree[a++];
        }
        if (b%2 == 0){
            s += tree[b--];
        }
        a /= 2;
        b /= 2;
    }
    return s;
}

void update(int k, int x){
    k += nc;
    tree[k] = x;
    k /= 2;
    while (k >= 1){
        tree[k] = tree[2*k] + tree[2*k+1];
        k /= 2;
    }
}

long long count_swaps(vector<int> s) {
    int n = s.size();
    vector<vector<int>> pos(n), neg(n);
    for (int i = 0; i<n; i++){
        int g = abs(s[i]);
        if (s[i] < 0){
            neg[g].push_back(i);
        }
        else{
            pos[g].push_back(i);
        }
    }
    for (int i = 0; i<n; i++){
        reverse(pos[i].begin(),pos[i].end());
        reverse(neg[i].begin(),neg[i].end());
    }
    nc = 1;
    while ((1<<nc) < n) nc++;
    nc = 1<<nc;
    tree.resize(2*nc);
    for (int i = 0; i<n; i++){
        tree[nc+i] = 1;
    }
    for (int i = nc-1; i>=1; i--){
        tree[i] = tree[2*i] + tree[2*i+1];
    }
    long long ans = 0;
    for (int i = 0; i<n; i++){
        int val = s[i];
        int g = abs(s[i]);
        if (s[i] > 0){
            if (pos[g].empty() || pos[g].back() != i) continue;
            pos[g].pop_back();
        }
        else{
            if (neg[g].empty() || neg[g].back() != i) continue;
            neg[g].pop_back();
        }
        int ind = -1;
        int rev = -s[i];
        if (rev > 0){
            ind = pos[g].back();
            pos[g].pop_back();
        }
        else{
            ind = neg[g].back();
            neg[g].pop_back();
        }
        ans += query(i+1,ind-1);
        if (s[i] > 0) ans++;
        update(i,0);
        update(ind,0);
    }
    return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:64:13: warning: unused variable 'val' [-Wunused-variable]
   64 |         int val = s[i];
      |             ^~~

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