제출 #1262399

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1262399		blueviolet	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	121 ms	21948 KiB

shoes

#include             <bits/stdc++.h>
    
#define             ll   long long
#define          io(x)   if (fopen(x".inp","r")) {freopen(x".inp","r",stdin),freopen(x".out","w",stdout);}
#define        TimeRun   {End=clock();cerr<<"Time run: "<<(float)(End-Begin)/CLOCKS_PER_SEC<<"s"<<el;}
#define      mem(c, x)   memset(c, x, sizeof(c))
#define         all(c)   c.begin(), c.end()
#define       bit(i,j)   ((i >> j) & 1)
#define             se   second     
#define             fi   first
#define             el   '\n'
using namespace std;  

template<class X, class Y> bool maximize(X &a, const Y &b) { return (a < b ? a = b, 1 : 0); }
template<class X, class Y> bool minimize(X &a, const Y &b) { return (a > b ? a = b, 1 : 0); }

int dx[8] = {0, 1, 0,-1, 1, 1,-1,-1};
int dy[8] = {1, 0,-1, 0, 1,-1,-1, 1};
const int  maxn  = 1e5 + 2;
const int  Inf   = 2e9 + 7;
const ll   Infll = 1e18 + 9;
const ll   Mod   = 1e9 + 7;
/*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*/
ll lz[maxn << 3], res;
pair<int,int> st[maxn << 3];
int n, valOfPos[maxn << 1];
vector<int> lstPos[maxn << 1];

int value(int val) {
	return val + n;
}

struct SegmentTree
{
    void down(int id, int l, int r) 
    {
        if (!lz[id]) return;

        lz[id << 1] += lz[id];
        lz[id << 1|1] += lz[id];

        st[id << 1].fi += lz[id];
        st[id << 1|1].fi += lz[id];

        lz[id] = 0;
    }

    void build(int id, int l, int r) 
    {
        if (l == r) {
            st[id] = {l, l};
            return;
        }
        int mid = l + r >> 1; 
        build(id << 1, l, mid);
        build(id << 1|1, mid + 1, r);
        st[id] = min(st[id << 1], st[id << 1|1]);
    }
    void update(int id, int l, int r, int u, int v, int val) 
    {
        if (l > v || r < u) return;
        if (u <= l && r <= v) {
            st[id].fi += val;
            lz[id] += val;
            return;
        }
        int mid = l + r >> 1; 
        down(id, l, r);
        update(id << 1, l, mid, u, v, val);
        update(id << 1|1, mid + 1, r, u, v, val);
        st[id] = min(st[id << 1], st[id << 1|1]);
    }

    int getPos(int id, int l, int r, int pos) 
    {
    	if (l == r) {
    		return st[id].fi;
    	}
        int mid = l + r >> 1; 
        down(id, l, r);
        if (pos <= mid)
         	return getPos(id << 1, l, mid, pos);
        return getPos(id << 1|1, mid + 1, r, pos);
    }
} seg;
long long count_swaps(vector<int> s) {
	n = (int)s.size() / 2;
	for (int i=1; i<=n*2; i++) valOfPos[i] = s[i-1];

	for (int i=n*2; i>=1; i--) {
		lstPos[value(valOfPos[i])].push_back(i);
	}

	seg.build(1, 1, n * 2);

	for (int i=1; i<=n * 2; i+=2) {	
		int valPos_i = valOfPos[st[1].se];
		int posR = lstPos[value(-valPos_i)].back();

		res += seg.getPos(1, 1, n * 2, posR) - i - 1 + (valPos_i > 0);
		seg.update(1, 1, n * 2, st[1].se + 1, posR-1, 1);
		seg.update(1, 1, n * 2, posR, posR, Inf);
		seg.update(1, 1, n * 2, st[1].se, st[1].se, Inf);

		lstPos[value(-valPos_i)].pop_back(); // lstPos giam dan
		lstPos[value(valPos_i)].pop_back();
	}
	return res;
}

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