Submission #341359

#	Time	Username	Problem	Language	Result	Execution time	Memory
341359		Killer2501	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	70 ms	19948 KiB

shoes

#include <bits/stdc++.h>
#define pb push_back
#define vii vector<int>
#define task "LAZY"
#define pll pair<ll, ll>
#define pii pair< pll, ll >
#define fi first
#define se second

using namespace std;
using ll = int;
using ull = unsigned long long;
const int N = 2e5+5;
const ll mod = 1e9+7;
const int base = 311;
ll m, n, k, t, T, ans, u, v, tong;
ll a[N], b[N], fe[N];
vector<ll> kq, lf[N], rt[N];
void add(ll id, ll val)
{
    for(; id <= n; id += id & -id)fe[id] += val;
}
ll get(ll id)
{
    ll total = 0;
    for(; id; id -= id & -id)total += fe[id];
    return total;
}
ll count_swaps(vector<ll> v)
{
    n = v.size();
    for(int i = n-1; i >= 0; i --)
    {
        if(v[i] < 0)lf[abs(v[i])].pb(i+1);
        else rt[abs(v[i])].pb(i+1);
    }
    for(int i = 1; i <= n; i ++)
    {
        if(b[i])continue;
        ll l = i, r;
        k = abs(v[i-1]);
        if(v[i-1] < 0)r = rt[k].back();
        else r = lf[k].back();
        lf[k].pop_back();
        rt[k].pop_back();
        ans += r + get(r) - (l + get(l)) - 1;
        if(v[l-1] > 0)++ans;
        b[r] = 1;
        //cout << l <<" "<<get(l)<<" "<<get(r)<<" "<<r<<'\n';
        add(l, 1);
        add(r+1, -1);
    }
    return ans;
}

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