Submission #185293

#	Time	Username	Problem	Language	Result	Execution time	Memory
185293		aggu_01000101	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	2 ms	376 KiB

shoes

#include <iostream>
#include <vector>
#include <shoes.h>
#include <map>
#include <unordered_map>
#define int long long
#define mid(l, u) ((l+u)/2)
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
using namespace std;
int query(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
    if(lazy[i]){
        segtree[i]+=(u-l+1)*lazy[i];
        if(l!=u){
            lazy[lchild(i)]+=lazy[i];
            lazy[rchild(i)]+=lazy[i];
        }
        lazy[i] = 0;
    }
    if(l>=ll && u<=uu) return segtree[i];
    if(l>uu || u<ll) return 0;
    return query(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + query(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int update(int l, int u, int i, int ll, int uu, int segtree[], int lazy[]){
    if(ll>uu) return 0;
    if(lazy[i]){
        segtree[i]+=(u-l+1)*lazy[i];
        if(l!=u){
            lazy[lchild(i)]+=lazy[i];
            lazy[rchild(i)]+=lazy[i];
        }
        lazy[i] = 0;
    }
    if(l>=ll && u<=uu){
        segtree[i] += (u-l+1);
        if(l!=u){
            lazy[lchild(i)]++;
            lazy[rchild(i)]++;
        }
        return segtree[i];
    }
    if(l>uu || u<ll) return segtree[i];
    return segtree[i] = update(l, mid(l, u), lchild(i), ll, uu, segtree, lazy) + update(mid(l, u)+1, u, rchild(i), ll, uu, segtree, lazy);
}
int count_swaps(vector<int32_t> s){
    int n = s.size();
    //cout<<n<<endl;
    int segtree[4*n], lazy[4*n];
    for(int i = 0;i<4*n;i++) segtree[i] = lazy[i] = 0;
    unordered_map<int, vector<int>> mp;
    for(int i = n-1;i>=0;i--){
        mp[s[i]].push_back(i);
    }
    int ans = 0;
    for(int i = 0;i<n;i++){
        //cout<<i<<" "<<mp[-s[i]][mp[-s[i]].size()-1]<<endl;
        if(mp[-s[i]][mp[-s[i]].size()-1]>i) continue;
        int oind = mp[-s[i]][mp[-s[i]].size()-1];
        int toadd;
        if(s[i]>0){
            toadd = i - oind - 1;
            toadd-=query(0, n-1, 0, oind, oind, segtree, lazy);
        }
        else{
            toadd = i - oind;
            toadd-=query(0, n-1, 0, oind, oind, segtree, lazy);
        }
        //cout<<i<<" "<<mp[-s[i]]<<" "<<toadd<<endl;
        ans+=toadd;
        update(0, n-1, 0, oind+1, i-1, segtree,lazy);
        mp[-s[i]].pop_back();
        mp[s[i]].pop_back();
    }
    cout<<ans<<endl;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:75:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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