Submission #1021137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021137		cpdreamer	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	784 ms	153632 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define V vector
struct segtree{
private:
    struct node{
        int sum;
        int len;
    };
    node neutral={0,0};
    static node merge(node a,node b){
        return{a.sum+b.sum,a.len+b.len};
    }
    static node modification(node a,int b){
        return{a.sum+a.len*b,a.len};
    }
    static int operation_modifier(int a,int b){
        return a+b;
    }
public:
    int size;
    V<node>query;
    V<int>operation;
    void init(int n) {
        size = 1;
        while (size < n)size *= 2;
        query.assign(2 * size, {0, 1});
        operation.assign(2 * size, 0);
    }
    void build(int x,int lx,int rx){
        if(rx-lx==1)
            return;
        int m=(lx+rx)/2;
        build(2*x+1,lx,m);
        build(2*x+2,m,rx);
        query[x]=merge(query[2*x+1],query[2*x+2]);
    }
    void build(){
        build(0,0,size);
    }
    void set(int l,int r,int v,int x,int lx,int rx){
        if(rx<=l || lx>=r)
            return;
        if(l<=lx && rx<=r){
            operation[x]=operation_modifier(operation[x],v);
            query[x]=modification(query[x],v);
            return;
        }
        int m=(lx+rx)/2;
        set(l,r,v,2*x+1,lx,m);
        set(l,r,v,2*x+2,m,rx);
        query[x]=modification(merge(query[2*x+1],query[2*x+2]),operation[x]);
    }
    void set(int l,int r,int v){
        set(l,r,v,0,0,size);
    }
    node calc(int l,int r,int x,int lx,int rx){
        if(rx<=l || lx>=r)
            return neutral;
        if(l<=lx && rx<=r)
            return query[x];
        int m=(lx+rx)/2;
        node a=calc(l,r,2*x+1,lx,m);
        node b=calc(l,r,2*x+2,m,rx);
        return modification(merge(a,b),operation[x]);
    }
    int calc(int l,int r){
        return calc(l,r,0,0,size).sum;
    }
    int get(int i){
        return calc(i,i+1);
    }
};
long long count_swaps(std::vector<int> s) {
    int n=(int)s.size();
    segtree tree;
    tree.init(n);
    tree.build();
    map<int,stack<int>>mp;
    bool vis[n];
    memset(vis,false,sizeof(vis));
    for(int i=n-1;i>=0;i--)
        mp[s[i]].push(i);
    long long c=0;
    for(int i=0;i<n;i+=2){
        int a;
        int ans=-1;
        int l=0,r=i-tree.get(i);
        while(l<=r){
            int m=l+(r-l)/2;
            if(m+tree.get(m)==i && !vis[m]){
                ans=m;
                break;
            }
            if(m+tree.get(m)>=i)
                r=m-1;
            else
                l=m+1;
        }
        a=s[ans];
        vis[mp[a].top()]=true;
        vis[mp[-1*a].top()]=true;
        int pos=mp[-1*a].top()+tree.get(mp[-1*a].top());
        c+=pos-i-1;
        if(a>0)
            c++;
        tree.set(mp[a].top(),mp[-1*a].top(),1);
        mp[-1*a].pop();
        mp[a].pop();
    }
    return c;
}

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