제출 #796912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
796912		HaroldVemeno	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	152 ms	140396 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int it[700000];
deque<int> lsl[100001];
deque<int> rsl[100001];
int n;
int l;

int query(int f, int t) {
    f += l;
    t += l;
    int r = 0;
    while(f < t) {
        if(f&1) r += it[f++];
        if(t&1) r += it[--t];
        f /= 2;
        t /= 2;
    }
    return r;
}

void pset(int s, int x) {
    s += l;
    it[s] = x;
    s /= 2;
    while(s > 0) {
        it[s] = it[2*s] + it[2*s+1];
        s /= 2;
    }
}

ll count_swaps(vector<int> ss) {
    n = ss.size();
    l = 1;
    ll ret = 0;
    for(int i = 0; i < n; ++i) {
        if(ss[i] > 0) rsl[ss[i]].push_back(i);
        else lsl[-ss[i]].push_back(i);
    }

    while(l < n) l *= 2;
    for(int i = 0; i < n; ++i)
        it[l+i] = 1;
    for(int i = l-1; i > 0; --i)
        it[i] = it[2*i] + it[2*i+1];
    for(int i = 0; i < n; ++i) {
        if(it[l+i] == 0) continue;
        int s = i;
        deque<int>& td = (ss[i] < 0 ? rsl : lsl)[abs(ss[i])];
        while(it[l+td.front()] == 0) td.pop_front();
        int t = td.front();
        pset(s, 0);
        pset(t, 0);
        D(query(s, t));
        ret += query(s, t);
        ifdeb for(int i = l; i < l+n; ++i) {
            cerr << it[i] << ' ';
        }
        ifdeb cerr << '\n';
        if(ss[i] > 0) ret += 1;
    }
    return ret;
}

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