Submission #539385

#	Time	Username	Problem	Language	Result	Execution time	Memory
539385		PiejanVDC	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	267 ms	279628 KiB

shoes

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

vector<int>st;

void build(int i, int j, int p) {
    if(i == j) {
        st[p] = 1;
        return;
    }
    int mid = (i+j)/2;
    build(i,mid,2*p);
    build(mid+1,j,2*p+1);
    st[p] = st[2*p] + st[2*p+1];
}

int l,r;

int query(int i, int j, int p) {
    if(i > r || j < l)
        return 0;
    if(i >= l && j <= r)
        return st[p];
    int mid = (i+j)/2;
    return query(i,mid,2*p) + query(mid+1,j,2*p+1);
}

void update(int i, int j, int p) {
    if(i > l || j < l)
        return;
    if(i == j) {
        assert(i == l);
        st[p]--;
        return;
    }
    int mid = (i+j)/2;
    update(i,mid,2*p);
    update(mid+1, j, 2*p+1);
    st[p] = st[2*p] + st[2*p+1];
}

long long count_swaps(vector<int>s) {
    const int n = (int)s.size();
    st.resize(8*n);
    vector<queue<int>>po(n+1);
    vector<queue<int>>ne(n+1);
    for(int i = 0 ; i < n ; i++) {
        if(s[i] > 0)
            po[s[i]].push(i);
        else
            ne[-s[i]].push(i);
    }
    build(0,n-1,1);
    int64_t ans = 0;
    for(int i = 0 ; i < n ; i++) {
        if(s[i] > 0) {
            if(po[s[i]].front() != i) continue;
            l = i, r = ne[s[i]].front();
            ans += query(0,n-1,1) - 2;
            l = r;
            update(0,n-1,1);
            ne[s[i]].pop();
            po[s[i]].pop();
            ans++;
        } else {
            if(ne[-s[i]].front() != i) continue;
            l = i, r = po[-s[i]].front();
            ans += query(0,n-1,1) - 2;
            l = r;
            update(0,n-1,1);
            po[-s[i]].pop();
            ne[-s[i]].pop();
        }
    }
    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