Submission #573367

#	Time	Username	Problem	Language	Result	Execution time	Memory
573367		talant117408	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	172 ms	35540 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 2e5+7;
int tree[N*4], lz[N*4];

void push(int v, int l, int r) {
    if (lz[v] != 0) {
        tree[v] += lz[v]*(r-l+1);
        if (l != r) {
            lz[v*2] += lz[v];
            lz[v*2+1] += lz[v];
        }
        lz[v] = 0;
    }
}

void update(int v, int l, int r, int ql, int qr) {
    push(v, l, r);
    if (ql > r || l > qr) return;
    if (ql <= l && r <= qr) {
        lz[v]++;
        push(v, l, r);
        return;
    }
    int mid = (l+r) >> 1;
    update(v*2, l, mid, ql, qr);
    update(v*2+1, mid+1, r, ql, qr);
    tree[v] = tree[v*2]+tree[v*2+1];
}

int get(int v, int l, int r, int pos) {
    push(v, l, r);
    if (l == r) return tree[v];
    int mid = (l+r) >> 1;
    if (pos <= mid) return get(v*2, l, mid, pos);
    else return get(v*2+1, mid+1, r, pos);
}

long long count_swaps(std::vector<int> s) {
    multiset <int> pos[sz(s)], neg[sz(s)];
    for (int i = 0; i < sz(s); i++) {
        if (s[i] < 0) neg[abs(s[i])].insert(i);
        else pos[abs(s[i])].insert(i);
    }
    vector <bool> used(sz(s));
    ll ans = 0;
    for (int i = 0; i < sz(s); i++) {
        if (used[i]) continue;
        int l = i + get(1, 0, sz(s)-1, i), r;
        if (s[i] < 0) {
            r = *pos[abs(s[i])].begin();
            used[r] = 1;
            if (i + 1 != r) {
                update(1, 0, sz(s)-1, i+1, r-1);
            }
            r += get(1, 0, sz(s)-1, r);
            ans += r-l-1;
        }
        else {
            r = *neg[abs(s[i])].begin();
            used[r] = 1; 
            if (i + 1 != r) {
                update(1, 0, sz(s)-1, i+1, r-1);
            }
            r += get(1, 0, sz(s)-1, r);
            ans += r-l;
        }
        neg[abs(s[i])].erase(neg[abs(s[i])].begin());
        pos[abs(s[i])].erase(pos[abs(s[i])].begin());
    }
    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