Submission #986873

#	Time	Username	Problem	Language	Result	Execution time	Memory
986873		PagodePaiva	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	289 ms	281944 KiB

shoes

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

using namespace std;
const int N = 400010;
queue <int> q[N];
int res[N];
int p[N];

struct Segtree{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return a+b;
	}
	void unlazy(int node, int l, int r){
		tree[node] += (r-l+1)*lazy[node];
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
		return;
	}
	void build(int node, int l,int r){
		if(l == r){
			tree[node] = 0;
			lazy[node] = 0;
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = 0;
		lazy[node] = 0;
		return;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node,tl,tr);
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node,tl,tr);
			return;
		}
		if(l > tr or tl > r) return;
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l <= tl and tr <= r) return tree[node];
		if(l > tr or tl > r) return 0;
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
} seg;

long long count_swaps(std::vector<int> v) {
	int n = v.size();
	int num = n;
	for(int i = v.size()-1;i >= 0;i--){
		if(q[v[i]+n].empty()){
			if(v[i] > 0){
				res[i+1] = num;
				q[n-v[i]].push(num-1);
			}
			else{
				res[i+1] = num-1;
				q[n-v[i]].push(num);
			}
			num -= 2;
		}
		else{
			res[i+1] = q[v[i]+n].front();
			q[v[i]+n].pop();
		}
	}
	seg.build(1, 1, n);
	for(int i = 1;i <= n;i++){
		// cout << res[i] << ' ';
		seg.update(1, res[i], res[i], 1, n, i);
	}
	int resp = 0;
	for(int i = n;i > 0;i--){
		resp += i - seg.query(1, i, i, 1, n);
		seg.update(1, seg.query(1, i, i, 1, n), i, 1, n, -1);
	}
	return resp;
}

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