Submission #842351

#	Time	Username	Problem	Language	Result	Execution time	Memory
842351		nasir_bashirov	Arranging Shoes (IOI19_shoes)	C++17	Compilation error	0 ms	0 KiB

shoes

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

#define int long long

#define db long double
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pii>
#define vll vector<pll>
#define all(x) x.begin(), x.end()
#define fastio\
    ios_base::sync_with_stdio(0);\
    cin.tie(0);\
    cout.tie(0)\

const int sz = 1e5 + 5;
int t[sz * 4], lazy[sz * 4], n;
map<int, deque<int>> mp;

void push(int x, int lx, int rx){
	if(lx == rx or t[x] == 0)	return;
	t[x * 2] += lazy[x], t[x * 2 + 1] += lazy[x];
	lazy[x * 2] += lazy[x], lazy[x * 2 + 1] += lazy[x];
	lazy[x] = 0;
}

void build(int x, int lx, int rx){
	if(lx == rx){
		t[x] = lx;
		return;
	}
	int mid = (lx + rx) / 2;
	build(x * 2, lx, mid);
	build(x * 2 + 1, mid + 1, rx);
	t[x] = max(t[x * 2], t[x * 2 + 1]);
}

void update(int l, int r, int v, int x, int lx, int rx){
	push(x, lx, rx);
	if(lx >= l and rx <= r){
		t[x] += v;
		lazy[x] += v;
		return;
	}
	if(lx > r or l > rx)	return;
	int mid = (lx + rx) / 2;
	update(l, r, v, x * 2, lx, mid);
	update(l, r, v, x * 2 + 1, mid + 1, rx);
	t[x] = max(t[x * 2], t[x * 2 + 1]);
}

int query(int l, int r, int x, int lx, int rx){
	push(x, lx, rx);
	if(lx >= l and rx <= r)	  return t[x];
	if(lx > r or l > rx)	return 0;
	int mid = (lx + rx) / 2;
	return max(query(l, r, x * 2, lx, mid), query(l, r, x * 2 + 1, mid + 1, rx));
}

int ind(int x){
	return query(x, x, 1, 1, n);
}

long long count_swaps(vi s) {
	n = s.size();
	vi used(n + 5, false);
	build(1, 1, n);
	long long res = 0;
	for(int i = 0; i < n; i++){
		int indd = -1;
		if(!mp[-s[i]].empty())	 indd = mp[-s[i]].front();	
		// cout << i << " " << indd << endl;
		if(indd != -1){
			res += ind(i + 1) - ind(indd + 1) - (s[i] > 0 ? 1 : 0);
			// cout << "ind  " << ind(i + 1) << " " << ind(indd + 1) << endl;
			update(indd + 1, i, 1, 1, 1, n);
			mp[-s[i]].pop_front();
		}
		else{
			mp[s[i]].push_back(i);
		}
	}
	return res;
}

// signed main() {
// 	int n;
// 	cin >> n;
// 	vector<int> v(2 * n);
// 	for(int i = 0; i < 2 * n; i++){
// 		cin >> v[i];
// 	}
// 	cout << "input ended" << endl;
// 	cout << count_swaps(v) << endl;
// }

Compilation message (stderr)

/usr/bin/ld: /tmp/ccvcHvDA.o: in function `main':
grader.cpp:(.text.startup+0x2a8): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status