Submission #267029

#	Time	Username	Problem	Language	Result	Execution time	Memory
267029		Dremix10	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	268 ms	35448 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#if dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x)
    #define p2(x,y)
    #define pp(x)
    #define pv(x)
    #define ppv(x)
#endif
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 1e18;
const int MOD = 1e9+7;
const int N = 2e5+1;


template<typename T>
struct SEGTREE{
    struct node{
        T val; // for adding more stuff

        node() : val(0) {}
        node(T _val) : val(_val) {}
    };
    vector<node> seg;
    int N;

    void init(int n){
        N = n;
        seg.assign(4*n,node());
    }

    node merge(node x, node y){
        node res;
        res.val = x.val + y.val;
        return res;
    }

    void build(int s, int e, int idx, T arr[]){
        if(s == e){
            seg[idx] = node(arr[s]);
            return;
        }
        int mid = (s+e)/2;
        build(s,mid,idx*2,arr);
        build(mid+1,e,idx*2+1,arr);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // supports 1-indexing
    void build(T arr[]){
        build(1,N,1,arr);
    }

    void update(int s, int e, int idx, int k, T val){
        if(s==e && s==k){
            seg[idx].val += val;
            return;
        }
        if(s>k || e<k)
            return;
        int mid = (s+e)/2;
        update(s,mid,idx*2,k,val);
        update(mid+1,e,idx*2+1,k,val);
        seg[idx] = merge(seg[idx*2],seg[idx*2+1]);
    }

    // arr[k] += val
    void update(int k, T val){
        update(1,N,1,k,val);
    }

    node query(int s, int e, int idx, int qs, int qe){
        if(qs<=s && e<=qe)
            return seg[idx];
        if(s>qe || e<qs)
            return node();
        int mid = (s+e)/2;
        return merge(query(s,mid,idx*2,qs,qe),query(mid+1,e,idx*2+1,qs,qe));
    }

    T query(int l, int r){
        return query(1,N,1,l,r).val;
    }

};

long long count_swaps(vector<int> s) {
    int i,n = s.size();

    int arr[n+1];
    for(i=1;i<=n;i++)arr[i]=1;

    SEGTREE<int> seg;
    seg.init(n);
    seg.build(arr);

    vector<set<int> > l(n+1);
    vector<set<int> > r(n+1);

    ll ans = 0;

    for(i=0;i<n;i++){
        if(s[i]<0)l[-s[i]].insert(i+1);
        else r[s[i]].insert(i+1);
    }
    for(i=1;i<=n/2;i++){
        pv(l[i])
        pv(r[i])
    }

    for(i=0;i<n;i++){
        if(seg.query(i+1,i+1)==0)continue;
        for(int j=1;j<=n/2;j++){
            pv(l[j])
            pv(r[j])
        }
        if(s[i]<0){
            int nxt = *(r[-s[i]].begin());
            ans += seg.query(1,nxt) - 2;
            p2(nxt,ans)
            seg.update(i+1,-1);
            seg.update(nxt,-1);
            r[-s[i]].erase(nxt);
            l[-s[i]].erase(i+1);
        }
        else{
            int nxt = *(l[s[i]].begin());
            ans += seg.query(1,nxt) - 1;
            p2(nxt,ans)
            seg.update(i+1,-1);
            seg.update(nxt,-1);
            r[s[i]].erase(i+1);
            l[s[i]].erase(nxt);
        }
    }
    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