Submission #808987

#	Time	Username	Problem	Language	Result	Execution time	Memory
808987		KemalK	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	98 ms	18552 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
  
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAX_N = 100000;
 
int n;
// left // right
vector<int> a[2][MAX_N+1];
int l[MAX_N+1], r[MAX_N+1];
bool used[MAX_N+1];
 
struct SEG{
    struct NODE{
        int l, r;
        int sum;
    };
    int SZ;
    vector<NODE> seg;
    void Init(int x){
        SZ = x;
        seg.push_back({-1, -1, 0});
        init(0, 0, SZ-1);
    }
    void init(int idx, int s, int e){
        if(s==e)    return;
        seg[idx].l = seg.size(); seg.push_back({-1, -1, 0});
        seg[idx].r = seg.size(); seg.push_back({-1, -1, 0});
        init(seg[idx].l, s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
    }
    void Update(int x, int y){
        update(0, 0, SZ-1, x, y);
    }
    void update(int idx, int s, int e, int x, int y){
        seg[idx].sum+=y;
        if(s==e){
			return;
		}
        if(x<=(s+e)/2){
			update(seg[idx].l, s, (s+e)/2, x, y);
		}
        else{
			update(seg[idx].r, (s+e)/2+1, e, x, y);
		}
    }
    int Sum(int x, int y){
        return sum(0, 0, SZ-1, x, y);
    }
    int sum(int idx, int s, int e, int x, int y){
        if(x<=s && e<=y){
			return seg[idx].sum;
		}
        else if(x>e || y<s){
			return 0;
		}
        return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
    }
};
 
SEG Seg;
 
int pair_find(int x){
    return (x>0) ? x : -x;
}
long long count_swaps(std::vector<int> S) {
    n = S.size();
    Seg.Init(n);
    for(int i=0; i<n; i++){
        Seg.Update(i+1, 1);
        if(S[i]<0){
            // left
            a[0][-S[i]].push_back(i);
        }else{
            a[1][S[i]].push_back(i);
            // right
        }
    }
    int idx = 1;
    for(int i=1; i<=n/2; i++){
        while(!a[1][i].empty()){
            r[idx] = a[1][i].back();
            l[idx] = a[0][i].back();
            S[a[1][i].back()] = idx;
            S[a[0][i].back()] = -idx;
            idx++; a[1][i].pop_back(); a[0][i].pop_back();
        }
    }
    ll ans = 0;
    for(int i=0; i<n; i++){
        if(used[pair_find(S[i])]){
            continue;
        }
        int now = pair_find(S[i]); 
        used[now] = true;
        if(S[i]<0){
            ans += (ll)Seg.Sum(i+1, r[now]-1);
            Seg.Update(r[now], -1);
        }else{
            ans += (ll)Seg.Sum(i+1, l[now]-1);
            Seg.Update(l[now], -1);
            ans++;
        }
    }
    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