Submission #185271

#	Time	Username	Problem	Language	Result	Execution time	Memory
185271		aggu_01000101	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	418 ms	28228 KiB

shoes

#include <iostream>
#include <shoes.h>
#include <vector>
#include <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;
    map<int, int> mp;
    for(int i = 0;i<n;i++) mp[s[i]] = i;
    int ans = 0;
    for(int i = 0;i<n;i++){
        if(mp[-s[i]]>i) continue;
        int toadd;
        if(s[i]>0){
            toadd = i - mp[-s[i]] - 1;
            toadd-=query(0, n-1, 0, mp[-s[i]], mp[-s[i]], segtree, lazy);
        }
        else{
            toadd = i - mp[-s[i]];
            toadd-=query(0, n-1, 0, mp[-s[i]], mp[-s[i]], segtree, lazy);
        }
        //cout<<i<<" "<<mp[-s[i]]<<" "<<toadd<<endl;
        ans+=toadd;
        update(0, n-1, 0, mp[-s[i]]+1, i-1, segtree,lazy);
    }
    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