Submission #398469

#	Time	Username	Problem	Language	Result	Execution time	Memory
398469		iulia13	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	55 ms	23880 KiB

shoes

#include <iostream>
#include <vector>
#include "shoes.h"
using namespace std;
const int nmax = 2e5 + 5;
#define ll long long
ll aib[nmax];
int moved[nmax], n;
vector <int> a[nmax];
int lsb(int x)
{
    return x & (-x);
}
void upd(int x, int val)
{
    for (x; x <= n; x += lsb(x))
        aib[x] += val;
}
ll qry(int x)
{
    ll s = 0;
    while (x)
    {
        s += aib[x];
        x -= lsb(x);
    }
    return s;
}
ll count_swaps(vector<int> v)
{
    ll i, ans = 0;
    n = v.size();
    for (i = n - 1; 0 <= i; i--)
        a[v[i] + n].push_back(i);
    for (i = 0; i < n; i++)
    {
        if (moved[i])
            continue;
        ll j = a[n - v[i]].back(), swaps = 0; ///i < j
        if (v[i] > 0)
            swaps = 1;
        swaps += j - i - 1 - (qry(j + 1) - qry(i + 1));
        upd(j + 1, 1);
        ans += swaps;
        moved[j] = 1;
        a[n - v[i]].pop_back();
        a[n + v[i]].pop_back();
    }
    return ans;
}/*
int main()
{
    int N, i;
    cin >> N;
    vector <int> v;
    v.resize(N);
    for (i = 0; i < N; i++)
        cin >> v[i];
    cout << count_swaps(v);
    return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'void upd(int, int)':
shoes.cpp:16:10: warning: statement has no effect [-Wunused-value]
   16 |     for (x; x <= n; x += lsb(x))
      |          ^

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