제출 #876413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
876413		Elvin_Fritl	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	0 ms	348 KiB

shoes

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

typedef long long ll;

const int N = 4e5 + 545 , inf = 1e9 + 12 , mod = 1e9 + 7;

       #include "shoes.h"

struct segtree {
	int tree[N*3] , lazy[N*3] , mark[N*3];
	void built(int v,int l,int r) {
		if(l == r) {
			tree[v] = 1;
			return;
		}
		int mid = (l + r)/2;
		built(v*2 , l , mid);
		built(v*2 + 1 , mid+1 , r);
		tree[v] = tree[v*2] + tree[v*2 + 1];
	}
	void push(int v,int l,int r) {
		if(mark[v] == 0) {
			return;
		}
		mark[v] = 0;
		int mid = (l+r)/2;
		lazy[v*2] = lazy[v*2 + 1] = lazy[v];
		mark[v*2] = 1;
		mark[v*2 + 1] = 1;
		tree[v*2] += (mid - l + 1)*lazy[v*2];
		tree[v*2] += (r - mid)*lazy[v*2 + 1];
	}
	void update(int v,int l,int r,int ml,int val) {
		if(r < ml) {
			return;
		}
		push(v , l , r);
		if(ml <= l) {
			mark[v] = 1;
			lazy[v] += val;
			tree[v] += val * (r - l + 1);
			return;
		}
		int mid = (l + r)/2;
		update(v , l , mid , ml , val);
		update(v , mid + 1 , r , ml , val);
		tree[v] = tree[v*2] + tree[v*2 + 1];
	}
	int get(int v,int l,int r,int ml) {
		if(r < ml) {
			return 0;
		}
		push(v , l , r);
		if(ml <= l) {
			return tree[v];
		}
		int mid = (l + r)/2;
		return (get(v , l , mid , ml) + get(v , mid + 1 , r , ml));
	}
};

segtree S;

ll count_swaps(vector<int> v) {
	int n = v.size();
	set<pair<int , int>> s;
	v.push_back(0);
	for(int i = 2*n;i>=1;i--){
		v[i] = v[i-1];
		s.insert({v[i] , i});
	}
	///cerr << "true1\n";
	S.built(1,1,2*n);
	ll res = 0;
	for(int i=1;i<=n;i++) {
		///cerr << "true2\n";
		if(s.find({v[i] , i}) != s.end()){
			///cerr << "true2\n";
			if(v[i] > 0) {
				res++;
			}
			auto it = s.lower_bound({-v[i] , i});
			if((*it).second - 2 >= i) {
				res += S.get(1,1,2*n,i + 2);
			}
			S.update(1 , 1 , 2*n , i, -1);
			S.update(1 , 1 , 2*n , (*it).second, -1);
			///cerr << "true3\n";
			if(s.find({v[i], i}) != s.end()){
				s.erase(s.find({v[i], i}));
			}
			///cerr << "true4\n";
			if(s.find({-v[i], (int)(*it).second}) != s.end()){
				s.erase(s.find({-v[i], (int)(*it).second}));
			}
			///cerr << "true5\n";
		}
	}
	return res;
}

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