Submission #535415

#	Time	Username	Problem	Language	Result	Execution time	Memory
535415		mario05092929	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	235 ms	142220 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,cnt,g;
int a[200005],c[200005],t[800005];
queue <int> wi[200005];

int query(int x,int l,int r,int rl,int rr) {
    if(rl > r||l > rr) return 0;
    if(rl <= l&&r <= rr) return t[x];
    int mid = (l + r) >> 1;
    return query(x*2,l,mid,rl,rr)+query(x*2+1,mid+1,r,rl,rr);
}

void update(int x,int l,int r,int wi) {
    if(wi < l||r < wi) return;
    if(l == r) {
        t[x] = 1; return;
    }
    int mid = (l + r) >> 1;
    update(x*2,l,mid,wi), update(x*2+1,mid+1,r,wi);
    t[x] = t[x*2]+t[x*2+1];
}

ll count_swaps(vector <int> s) {
    n = s.size(); n /= 2;
    for(int i = 1;i <= 2*n;i++) a[i] = s[i-1];
    for(int i = 1;i <= 2*n;i++) {
        wi[a[i]+n].push(i);
    }
    ll ans = 0;
    for(int i = 1;i <= 2*n;i++) {
        if(c[i]) continue;
        int x = a[i];
        //cout << i << ' ' << wi[-x+n].front() << '\n';
        if(x < 0) {
            ans += wi[-x+n].front()-i-query(1,1,2*n,i+1,wi[-x+n].front())-1;
        }
        else {
            ans += wi[-x+n].front()-i-query(1,1,2*n,i+1,wi[-x+n].front());
        }
        update(1,1,2*n,wi[-x+n].front());
        update(1,1,2*n,i);
        c[i] = c[wi[-x+n].front()] = 1;
        wi[-x+n].pop();
        wi[x+n].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