Submission #670646

#	Time	Username	Problem	Language	Result	Execution time	Memory
670646		birthdaycake	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	320 ms	30688 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
using namespace std;

int N,Left,Right,V;
long long seg[1 << 19];


long long Query(int l = 1, int r = N, int ind = 1){
    if(l > Right or r < Left) return 0;
    if(l >= Left && r <= Right) {
        return seg[ind];
    }
    int mid = (l + r) / 2;
    return Query(l, mid, ind * 2) + Query(mid + 1, r, ind * 2 + 1);
}
void Update(int Pos, int V){
    int ind = N + Pos - 1;
    seg[ind] += V;
    while(ind /= 2) seg[ind] = seg[ind * 2] + seg[ind * 2 + 1];
}
long long count_swaps(vector<int>s) {
    
    int n = s.size(); long long ans = 0;
    map<int,set<int>>d;
    N = exp2(ceil(log2(n)));
    memset(seg, 0, sizeof seg);
    for(int i = 0; i < n; i++) Update(i + 1, 1);
    
    
    for(int i = 0; i < n; i++){
        int f = -1;
        if(d[-s[i]].size()){
            f = *d[-s[i]].begin();
        }
        if(f != -1){
            Left = 1; Right = f + 1;
            int x = Query(), y = 0;
            Right = i + 1;
            y = Query();
            ans += (y - x);
            if(s[i] > 0) ans--;
            Update(f + 2, 1);
            Update(i + 1, -1);
            d[-s[i]].erase(f);
        }else{
            d[s[i]].insert(i);
        }
        
    }
    
    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