Submission #1246857

#	Time	Username	Problem	Language	Result	Execution time	Memory
1246857		sofiefu	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	389 ms	31720 KiB

shoes

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

#define int long long
#define vo vector
#define pb push_back
#define fi first 
#define se second 
#define all(x) x.begin(), x.end()

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define repd(i, a, b) for(int i=(b-1); i>=(a); i--)
#define pr(x) cerr << #x << " = " << x << endl;
int const inf = 1e18, mxn = 2e5+4;
int n;

struct segtree{
    vi seg;
    int n;
    segtree(int _n): n(_n), seg(_n*4, 0){}

    void upd(int v, int l, int r, int pos, int add){
        if(l==r) {seg[v]+=add; return;}
    
        int mid = (l+r)/2;
        if(pos<=mid) upd(v*2+1, l, mid, pos, add);
        else upd(v*2+2, mid+1, r, pos, add);
        seg[v] = seg[v*2+1] + seg[v*2+2];
    }
    
    int qry(int v, int l, int r, int ql, int qr){
        if(ql<=l && r<=qr) return seg[v];
        if(ql>r || l>qr) return 0;
    
        int mid = (l+r)/2;
        return qry(2*v+1, l, mid, ql, qr) + qry(2*v+2, mid+1, r, ql, qr);
    } 
};

int count_swaps(vector<signed> inp){
    n = inp.size()/2;
    vi fixed(2*n);

    map<int, vi> occ;
    segtree seg(2*n);
    repd(i, 0, 2*n){
        seg.upd(0, 0, seg.n-1, i, 1);
        occ[inp[i]].pb(i);
    }

    int i = 0, ans = 0;
    while(i<2*n){
        if(fixed[i]) {i++; continue;}
        int x = inp[i];

        vi &tmp = occ[-x];
        int nex = tmp.back(); tmp.pop_back(); occ[x].pop_back();
        fixed[i] = fixed[nex] = 1;

        seg.upd(0, 0, seg.n-1, i, -1); seg.upd(0, 0, seg.n-1, nex, -1);
        if(x<0) ans += seg.qry(0, 0, seg.n-1, i, nex);
        else ans += seg.qry(0, 0, seg.n-1, i, nex) + 1;
        i++; 
    }

    return ans;
}

/*
3
-1 -1 -3 1 1 3

svar: 2+2+1=5 
*/ 

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