Submission #1031249

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1031249	2024-07-22T16:25:26 Z	Lalic	Rectangles (IOI19_rect)	C++17	Compilation error	0 ms	0 KB

rect

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

#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define mp make_pair

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<double> cd;

const int MAXN = 2e5+10;
const ll LINF = 0x3f3f3f3f3f3f3f3f;

int N;
ll tree[MAXN];

void upd(int p){ for(;p<=2*N;p+=(p&-p)) tree[p]++; }
ll query(int p){
	ll ret=0;
	for(;p>0;p-=(p&-p)) ret+=tree[p];
	return ret;
}

void coordinateCompression(vector<int>& arr){
	vector<int> proc;
	for(auto u : arr) proc.pb(abs(u));
	
	sort(all(proc));
	proc.erase(unique(all(proc)), proc.end());
	
	map<int, int> comp;
	for(int i=0;i<(int)proc.size();i++) comp[proc[i]]=i+1;
	
	for(auto& u : arr){
		if(u<0) u=-comp[-u];
		else u=comp[u];
	}
}

ll count_swaps(vector<int> s) {
	N=((int)s.size())>>1;
	
	coordinateCompression(s);
	
	vector<queue<int>> occ(N+1), aux(N+1);
	vector<int> left;
	for(int i=0;i<2*N;i++){
		if(s[i]>0) occ[s[i]].push(i+1), aux[s[i]].push(i+1);
		else left.pb(i+1);
	}
	
	vector<pii> proc;
	for(auto u : left){
		int id=-s[u-1];
		proc.pb({u+aux[id].front(), u});
		aux[id].pop();
	}
	
	left.clear();
	
	sort(all(proc));
	for(auto [u, v]: proc) left.pb(v);
	
	
	ll ans=0;
	for(int i=0;i<N;i++){
		ll curr=left[i]-query(left[i])-1;
		upd(left[i]);
		
		int id=abs(s[left[i]-1]);
		curr+=occ[id].front()-query(occ[id].front())-1;
		upd(occ[id].front());
		occ[id].pop();
		
		ans+=curr;
	}
	
	return ans;
}

Compilation message

rect.cpp:1:10: fatal error: shoes.h: No such file or directory
    1 | #include "shoes.h"
      |          ^~~~~~~~~
compilation terminated.