oj.uz

답안 #624350

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
624350 2022-08-08T02:54:23 Z Temmie 고대 책들 (IOI17_books) C++17
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>

struct Seg {
	
	int size;
	std::vector <int> min;
	std::vector <int> max;
	
	Seg(int s) {
		size = 1;
		while (size < s) {
			size <<= 1;
		}
		max.resize(size << 1, -1);
		min.resize(size << 1, 1 << 30);
	}
	
	inline void build(const std::vector <int>& mn, const std::vector <int>& mx) {
		build(mn, mx, 0, 0, size);
	}
	
	void build(const std::vector <int>& mn, const std::vector <int>& mx, int now, int l, int r) {
		if (!(r - l - 1)) {
			if (l < (int) mn.size()) {
				min[now] = mn[l];
			}
			if (l < (int) mx.size()) {
				max[now] = mx[l];
			}
			return;
		}
		int mid = (l + r) >> 1;
		build(mn, mx, now * 2 + 1, l, mid);
		build(mn, mx, now * 2 + 2, mid, r);
		max[now] = std::max(max[now * 2 + 1], max[now * 2 + 2]);
		min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
	}
	
	inline int query_min(int l, int r) {
		return query_min(l, r, 0, 0, size);
	}
	
	int query_min(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 1 << 30;
		}
		if (l >= tl && r <= tr) {
			return min[now];
		}
		int mid = (l + r) >> 1;
		return std::min(query_min(tl, tr, now * 2 + 1, l, mid), query_min(tl, tr, now * 2 + 2, mid, r));
	}
	
	inline int query_max(int l, int r) {
		return query_max(l, r, 0, 0, size);
	}
	
	int query_max(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return -1;
		}
		if (l >= tl && r <= tr) {
			return max[now];
		}
		int mid = (l + r) >> 1;
		return std::max(query_max(tl, tr, now * 2 + 1, l, mid), query_max(tl, tr, now * 2 + 2, mid, r));
	}
	
};

struct Cycle {
	std::vector <int> c;
	int l, r;
};

long long minimum_walk(std::vector <int> p, int s) {
	int n = p.size();
	while (s < (int) p.size() - 1 && p[n - 1] == n - 1) {
		p.pop_back();
	}
	int begrem = 0;
	while (begrem < s && p[begrem] == begrem) {
		begrem++;
	}
	p.erase(p.begin(), p.begin() + begrem);
	n = p.size();
	if (!n) {
		return 0;
	}
	std::vector <bool> vis(n, false);
	std::vector <Cycle> cyc;
	std::vector <int> part(n, -1);
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (vis[i]) {
			continue;
		}
		vis[i] = true;
		int part_now = cyc.size();
		cyc.resize(cyc.size() + 1);
		cyc.back().c = { i };
		cyc.back().l = cyc.back().r = i;
		ans += abs(i - p[i]);
		int v = p[i];
		part[i] = part_now;
		while (v != i) {
			vis[v] = true;
			cyc.back().c.push_back(v);
			cyc.back().l = std::min(cyc.back().l, v);
			cyc.back().r = std::max(cyc.back().r, v);
			part[v] = part_now;
			ans += abs(v - p[v]);
			v = p[v];
		};
	}
	Seg seg(n);
	std::vector <int> mn(n), mx(n);
	for (int i = 0; i < n; i++) {
		mn[i] = cyc[part[i]].l;
		mx[i] = cyc[part[i]].r;
	}
	seg.build(mn, mx);
	int cmps = 0;
	int l = 0, r = 0;
	int last;
	while (r < n) {
		while ((last = seg.query_max(l, r + 1)) > r) {
			r = last;
		}
		l = ++r;
		cmps++;
	}
	int ll = cyc[part[s]].l;
	int rr = cyc[part[s]].r;
	l = s, r = s;
	int last_l, last_r;
	cmps--;
	while (l >= ll) {
		while (true) {
			last_l = seg.query_min(l, r + 1);
			last_r = seg.query_max(l, r + 1);
			if (last_l >= l && last_r <= r) {
				break;
			}
			l = last_l;
			r = last_r;
		}
		l--;
		r++;
		cmps++;
	}
	return ans + (cmps - 1) * 2;
}

Compilation message

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:134:6: warning: unused variable 'rr' [-Wunused-variable]
  134 |  int rr = cyc[part[s]].r;
      |      ^~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '0'
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '0'
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '0'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2744'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 296 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB 3rd lines differ - on the 1st token, expected: '4', found: '0'
11 Halted 0 ms 0 KB -