제출 #710756

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

shoes

//#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <functional>
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

#define mp make_pair
#define f first
#define s second
#define pb push_back

typedef long long ll;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const lld pi = 3.14159265358979323846;

#define MAXI (int)2e5+5


// Entweder rechts oder unten -> dann nehmen oder nicht nehmen.

struct segtree{
	int size;
	vector<int> tree;
	
	void init(int n){
		int c = 1;
		while(c < n) c*=2;
		size = c;
		tree.assign(size,0);
	}
	
	int query(int i,int x,int lx,int rx){
		if(rx-lx==1) return tree[x];
		int mid = (lx+rx)/2;
		if(i<=mid) return tree[x]+query(i,2*x+1,lx,mid);
		else return tree[x]+query(i,2*x+2,mid,rx);
	}
	
	void update(int val,int l,int r,int x,int lx,int rx){
		if(l>r) return;
		if(lx >= r || rx <= l) return;
		if(lx >= l && rx <= r){
			tree[x]+=val;
			return;
		}
		int mid = (lx+rx)/2;
		update(val,l,r,2*x+1,lx,mid);
		update(val,l,r,2*x+2,mid,rx);
	}
};

long long count_swaps(vector<int> a){
	
	int n = a.size();
	vector<set<int>> left(4*n+1);
	vector<set<int>> right(4*n+1);
	for(int i = 0;i<n;i++){
		if(a[i] < 0){
			int x = a[i]*-1;
			left[x].insert(i);
		}else right[a[i]].insert(i);
	}
	
	segtree s; s.init(4*n);
	vector<bool> marked(2*n,0);
	ll ans = 0;
	for(int i = 0;i<n;i++){
		if(marked[i]) continue;
		//Linker Schuh
		if(a[i]  < 0){
			int x = a[i]*-1;
			int indexRechts = *right[x].begin(); 
			int wertRechts = indexRechts + s.query(indexRechts,0,0,s.size);
			
			
			int wertLinks = i + s.query(i,0,0,s.size);
			ans = ans + wertRechts- wertLinks  - 1 ;
			s.update(1,i,indexRechts-1,0,0,s.size);
			right[x].erase(indexRechts);
			left[x].erase(i);
			marked[indexRechts] = 1;
			marked[i] = 1;
		}else{
			int x = a[i];
			int indexLinks = *left[x].begin(); 
			marked[indexLinks] = 1;
			marked[i] = 1;
			int wertLinks = indexLinks + s.query(indexLinks,0,0,s.size);
			int wertRechts = i + s.query(i,0,0,s.size);
			ans = ans + wertLinks - wertRechts;
			s.update(1,i,indexLinks-1,0,0,s.size);
			left[x].erase(indexLinks);
			right[x].erase(i);
		}
		//cout << ans << " ";
	}
	return ans;
}

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