Submission #144338

#	Time	Username	Problem	Language	Result	Execution time	Memory
144338		CodeKracker	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	2 ms	376 KiB

shoes

/*input

*/
/**
    Author: Kristopher Paul
    Date Created: 16-08-2019
    Contest Name:
                _/    _/   _/_/_/_/   _/   _/_/_/_/
               _/  _/     _/    _/   _/   _/
              _/_/       _/_/_/_/   _/   _/_/_/_/
             _/  _/     _/  _/     _/         _/
            _/    _/   _/    _/   _/   _/_/_/_/
**/
#include<iostream>
#include<unordered_map>
#include<vector>
#include<cmath>
#define ll long long
#define pb push_back
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define umap unordered_map
#define vi vector<int>
using namespace std;

struct segnode
{
    int lazy;
    int val;
};

segnode tree[400005];

void build(int node,int s,int e){
    if(s == e){
        tree[node].lazy = 0;
        tree[node].val = 0;
        return;
    }
    int m = (s+e)/2;
    build(node*2,s,m);
    build(node*2+1,m+1,e);
    tree[node].lazy = 0;
    tree[node].val = 0;
}

void upd(int node,int s,int e,int l,int r,int v){
    if(tree[node].lazy != 0){
        tree[node].val += (tree[node].lazy*(e-s+1));
        if(s != e){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
    if(s > r || e < l || s > e || l > r){
        return;
    }
    if(l <= s && e <= r){
        tree[node].val += (v*(e-s+1));
        if(s != e){
            tree[node*2].lazy += v;
            tree[node*2+1].lazy += v;
        }
        return;
    }
    int m = (s+e)/2;
    upd(node*2,s,m,l,r,v);
    upd(node*2+1,m+1,e,l,r,v);
    tree[node].val = tree[node*2].val + tree[node*2+1].val;
}

int query(int node,int s,int e,int pos){
    if(tree[node].lazy != 0){
        tree[node].val += (tree[node].lazy*(e-s+1));
        if(s != e){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
    if(s > pos || e < pos || s > e){
        return 0;
    }
    if(s == pos && pos == e){
        return tree[node].val;
    }
    int m = (s+e)/2;
    int a = query(node*2,s,m,pos);
    int b = query(node*2+1,m+1,e,pos);
    tree[node].val = tree[node*2].val + tree[node*2+1].val;
    return max(a,b);
}

ll count_swaps(vector<int> arr){
    int n = arr.size();
    build(1,1,n);
    umap<int,vi> op;
    bool done[n+1] = {};
    FORD(i,n-1,0){
        op[arr[i]].pb(i+1);
    }
    ll ans = 0;
    FOR(i,0,n){
        if(done[i+1]){
            continue;
        }
        if(arr[i] < 0){
            vi::iterator k = op[abs(arr[i])].end();
            k--;
            int pos = *k;
            int rpos = query(1,1,n,pos) + pos;
            done[pos] = true;
            int lpos = i+1;
            ans += rpos-lpos-1;
            upd(1,1,n,lpos+1,rpos-1,1);
            upd(1,1,n,rpos,rpos,rpos-lpos-1);
            op[abs(arr[i])].pop_back();
            op[arr[i]].pop_back();
        }else if(arr[i] > 0){
            vi::iterator k = op[-arr[i]].end();
            k--;
            int pos = *k;
            done[pos] = true;
            int rpos = i+1;
            int lpos = query(1,1,n,pos) + pos;
            ans += lpos-rpos;
            upd(1,1,n,rpos,lpos-1,1);
            upd(1,1,n,lpos,lpos,lpos-rpos);
            op[-arr[i]].pop_back();
            op[arr[i]].pop_back();
        }
    }
    return ans;
}

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