oj.uz

Submission #693086

# Submission time Handle Problem Language Result Execution time Memory
693086 2023-02-02T11:14:05 Z whqkrtk04 Ancient Books (IOI17_books) C++17
12 / 100
 1 ms 340 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

template <typename node_seg, typename node_query = node_seg, typename index_t = int>
class Segtree {
	private:
	const size_t n;
	std::vector<node_seg> seg;

	void init(const size_t i, const index_t s, const index_t e, const std::vector<node_seg> &A) {
		if(s+1 == e) seg[i] = A[s];
		else {
			init(i<<1, s, s+e>>1, A);
			init(i<<1|1, s+e>>1, e, A);
			seg[i] = seg[i<<1]+seg[i<<1|1];
		}
	}

	void update(const size_t i, const index_t s, const index_t e, const index_t j, const node_query &x) {
		if(j >= e || s > j) return;
		if(s+1 == e) seg[i] += x;
		else {
			update(i<<1, s, s+e>>1, j, x);
			update(i<<1|1, s+e>>1, e, j, x);
			seg[i] = seg[i<<1]+seg[i<<1|1];
		}
	}

	node_seg query(const size_t i, const index_t s, const index_t e, const index_t l, const index_t r) const {
		if(e <= l || r <= s) return node_seg::inf();
		if(l <= s && e <= r) return seg[i];
		return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
	}

	public:
	Segtree(const int n) : n(n) {
		seg.resize(4*n, node_seg::inf());
	}
	Segtree(const std::vector<node_seg> &A) : n(A.size()) {
		seg.resize(4*n, node_seg::inf());
		init(1, 0, n, A);
	}
	void update(const index_t j, const node_query &x) { update(1, 0, n, j, x); }
	node_seg query(const index_t l, const index_t r) const { return query(1, 0, n, l, r); }
};

struct Node_min {
	int x;
	static Node_min inf() { return {INF}; }
	Node_min operator+(const Node_min &y) { return {min(x, y.x)}; }
	void operator+=(const Node_min &y) { x = min(x, y.x); }
};

struct Node_max {
	int x;
	static Node_max inf() { return {-INF}; }
	Node_max operator+(const Node_max &y) { return {max(x, y.x)}; }
	void operator+=(const Node_max &y) { x = max(x, y.x); }
};

ll minimum_walk(vector<int> p, int s) {
	ll ans = 0LL;
	for(int i = 0; i < p.size(); i++) ans += abs(i-p[i]);
	int n = p.size();
	vector<vector<int>> A;
	vector<int> B(n);
	vector<bool> vis(n, false);
	for(int i = 0; i < n; i++) {
		if(vis[i]) continue;
		vector<int> T;
		int tmp = i;
		do {
			T.push_back(tmp);
			B[tmp] = A.size();
			vis[tmp] = true;
			tmp = p[tmp];
		} while(tmp != i);
		A.push_back(T);
	}
	vector<Node_min> min_nodes(n, Node_min::inf());
	vector<Node_max> max_nodes(n, Node_max::inf());
	for(int i = 0; i < A.size(); i++) {
		int l = *min_element(A[i].begin(), A[i].end());
		int r = *max_element(A[i].begin(), A[i].end());
		for(auto j : A[i]) {
			min_nodes[j].x = l;
			max_nodes[j].x = r+1;
		}
	}
	Segtree<Node_min> seg_min(min_nodes);
	Segtree<Node_max> seg_max(max_nodes);
	int l = s, r = s+1;
	while(l > 0 && p[l-1] == l-1) l--;
	while(r < n && p[r] == r) r++;
	while(l > 0 || r < n) {
		int mi = seg_min.query(l, r).x;
		int ma = seg_max.query(l, r).x;
		if(mi == l && ma == r) {
			ans += 2;
			if(r == n) l--;
			else r++;
		} else l = mi, r = ma;
		while(l > 0 && p[l-1] == l-1) l--;
		while(r < n && p[r] == r) r++;
	}
	return ans;
}

Compilation message

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < p.size(); i++) ans += abs(i-p[i]);
      |                 ~~^~~~~~~~~~
books.cpp:97:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |  for(int i = 0; i < A.size(); i++) {
      |                 ~~^~~~~~~~~~
books.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = Node_min; node_query = Node_min; index_t = int; size_t = long unsigned int]':
books.cpp:56:3:   required from 'Segtree<node_seg, node_query, index_t>::Segtree(const std::vector<_Tp>&) [with node_seg = Node_min; node_query = Node_min; index_t = int]'
books.cpp:105:37:   required from here
books.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |    init(i<<1, s, s+e>>1, A);
      |                  ~^~
books.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |    init(i<<1|1, s+e>>1, e, A);
      |                 ~^~
books.cpp: In instantiation of 'void Segtree<node_seg, node_query, index_t>::init(size_t, index_t, index_t, const std::vector<_Tp>&) [with node_seg = Node_max; node_query = Node_max; index_t = int; size_t = long unsigned int]':
books.cpp:56:3:   required from 'Segtree<node_seg, node_query, index_t>::Segtree(const std::vector<_Tp>&) [with node_seg = Node_max; node_query = Node_max; index_t = int]'
books.cpp:106:37:   required from here
books.cpp:28:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |    init(i<<1, s, s+e>>1, A);
      |                  ~^~
books.cpp:29:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |    init(i<<1|1, s+e>>1, e, A);
      |                 ~^~
books.cpp: In instantiation of 'node_seg Segtree<node_seg, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) const [with node_seg = Node_min; node_query = Node_min; index_t = int; size_t = long unsigned int]':
books.cpp:59:71:   required from 'node_seg Segtree<node_seg, node_query, index_t>::query(index_t, index_t) const [with node_seg = Node_min; node_query = Node_min; index_t = int]'
books.cpp:111:30:   required from here
books.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                         ~^~
books.cpp:47:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                     ~^~
books.cpp: In instantiation of 'node_seg Segtree<node_seg, node_query, index_t>::query(size_t, index_t, index_t, index_t, index_t) const [with node_seg = Node_max; node_query = Node_max; index_t = int; size_t = long unsigned int]':
books.cpp:59:71:   required from 'node_seg Segtree<node_seg, node_query, index_t>::query(index_t, index_t) const [with node_seg = Node_max; node_query = Node_max; index_t = int]'
books.cpp:112:30:   required from here
books.cpp:47:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                         ~^~
books.cpp:47:54: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   return query(i<<1, s, s+e>>1, l, r)+query(i<<1|1, s+e>>1, e, l, r);
      |                                                     ~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1128'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1128'
23 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '3304', found: '2910'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '1128'
23 Halted 0 ms 0 KB -