제출 #1290702

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290702		kahoul	Arranging Shoes (IOI19_shoes)	C++20	컴파일 에러	0 ms	0 KiB

shoes

#include "shoes.h"

using namespace std;
typedef pair<int, int> pii;

const int maxn = 1e5 + 10;
multiset<int> seg[4 * maxn];
int ind[4 * maxn];
int lz[4 * maxn];

vector<int> thing;

void propagate (int idx, int l, int r) {
	if (lz[idx] == 0) return;

	int lazy = lz[idx];
	lz[idx] = 0;

	if (l == r) {
		if (ind[idx] == -1) return;
		ind[idx] += lazy;
		return;
	}

	lz[idx * 2] += lazy;
	lz[idx * 2 + 1] += lazy;
}

void build (int idx, int l, int r) {
	if (l == r) {
		ind[idx] = l;
		seg[idx].insert(thing[l]);
		return;
	}

	int m = (l + r) >> 1;
	build(idx * 2, l, m);
	build(idx * 2 + 1, m + 1, r);
	for (auto v : seg[idx * 2]) {
		seg[idx].insert(v);
	}
	for (auto v : seg[idx * 2 + 1]) {
		seg[idx].insert(v);
	}
}

void update (int idx, int l, int r, int i, int j) {
	propagate(idx, l, r);

	if (j < l || r < i) return;
	if (i <= l && r <= j) {
		lz[idx]++;
		propagate(idx, l, r);
		return;
	}

	int m = (l + r) >> 1;
	update(idx * 2, l, m, i, j);
	update(idx * 2 + 1, m + 1, r, i, j);
}

void remove_elm (int idx, int l, int r, int i) {
	propagate(idx, l, r);

	if (i < l || r < i) return;
	if (l == r) {
		seg[idx].erase(thing[i]);
		ind[idx] = -1;
		return;
	}

	int m = (l + r) >> 1;
	remove_elm(idx * 2, l, m, i);
	remove_elm(idx * 2 + 1, m + 1, r, i);
	seg[idx].erase(seg[idx].find(thing[i]));
}

int query_idx (int idx, int l, int r, int i) {
	propagate(idx, l, r);

	if (l == r) return ind[idx];

	int m = (l + r) >> 1;
	if (i <= m) return query_idx(idx * 2, l, m, i);
	else return query_idx(idx * 2 + 1, m + 1, r, i);
}

pair<int, int> query_find (int idx, int l, int r, int x) {
	propagate(idx, l, r);

	if (l == r) return {ind[idx], l};

	int m = (l + r) >> 1;
	if (seg[idx * 2].count(x) > 0) return query_find(idx * 2, l, m, x);
	else return query_find(idx * 2 + 1, m + 1, r, x);
}

long long count_swaps(vector<int> s) {
	thing.push_back(0);

	int n = s.size();
	deque<pair<int, int>> q;

	for (int i = 1; i <= s.size(); i++) {
		thing.push_back(s[i - 1]);
		q.push_back({s[i - 1], i});
	}

	build(1, 1, n);

	for (int i = 1; i <= n; i++) {
		//cout << thing[i] << ' ';
	}
	//cout << '\n';

	for (int i = 1; i <= n; i++) {
		//cout << query_idx(1, 1, n, i) << ' ';
	}
	//cout << '\n';

	int ans = 0;

	while (!q.empty()) {
		auto [v, i] = q.front();
		q.pop_front();

		int idx = query_idx(1, 1, n, i);

		if (idx == -1) continue;

		auto [nidx, nreal] = query_find(1, 1, n, -v);

		remove_elm(1, 1, n, i);
		remove_elm(1, 1, n, nreal);
		update(1, 1, n, i, nreal);
		//cout << nidx << ' ' << idx << ' ' << nreal << '\n';

		int delta = nidx - idx - 1;

		if (v > 0) delta++;

		//cout << delta << '\n';
		ans += delta;
	}

	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

shoes.cpp:7:1: error: 'multiset' does not name a type
    7 | multiset<int> seg[4 * maxn];
      | ^~~~~~~~
shoes.cpp: In function 'void build(int, int, int)':
shoes.cpp:32:17: error: 'seg' was not declared in this scope
   32 |                 seg[idx].insert(thing[l]);
      |                 ^~~
shoes.cpp:39:23: error: 'seg' was not declared in this scope
   39 |         for (auto v : seg[idx * 2]) {
      |                       ^~~
shoes.cpp:42:23: error: 'seg' was not declared in this scope
   42 |         for (auto v : seg[idx * 2 + 1]) {
      |                       ^~~
shoes.cpp: In function 'void remove_elm(int, int, int, int)':
shoes.cpp:67:17: error: 'seg' was not declared in this scope
   67 |                 seg[idx].erase(thing[i]);
      |                 ^~~
shoes.cpp:75:9: error: 'seg' was not declared in this scope
   75 |         seg[idx].erase(seg[idx].find(thing[i]));
      |         ^~~
shoes.cpp: In function 'std::pair<int, int> query_find(int, int, int, int)':
shoes.cpp:94:13: error: 'seg' was not declared in this scope
   94 |         if (seg[idx * 2].count(x) > 0) return query_find(idx * 2, l, m, x);
      |             ^~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:102:9: error: 'deque' was not declared in this scope
  102 |         deque<pair<int, int>> q;
      |         ^~~~~
shoes.cpp:2:1: note: 'std::deque' is defined in header '<deque>'; did you forget to '#include <deque>'?
    1 | #include "shoes.h"
  +++ |+#include <deque>
    2 | 
shoes.cpp:102:28: error: expected primary-expression before '>' token
  102 |         deque<pair<int, int>> q;
      |                            ^~
shoes.cpp:102:31: error: 'q' was not declared in this scope
  102 |         deque<pair<int, int>> q;
      |                               ^
shoes.cpp: In function 'std::pair<int, int> query_find(int, int, int, int)':
shoes.cpp:93:13: warning: control reaches end of non-void function [-Wreturn-type]
   93 |         int m = (l + r) >> 1;
      |             ^