QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#423914#8578. 과일 게임zhaohaikun0 459ms34440kbC++206.2kb2024-05-28 19:10:592024-05-28 19:10:59

Judging History

你现在查看的是最新测评结果

  • [2024-05-28 19:10:59]
  • 评测
  • 测评结果：0
  • 用时：459ms
  • 内存：34440kb
查看
  • [2024-05-28 19:10:59]
  • 提交

answer

// MagicDark
#include <bits/stdc++.h>
#define deque vector
#define mid ((l + r) >> 1)
#define ls num << 1
#define rs ls | 1
#define li ls, l, mid
#define ri rs, mid + 1, r
#define debug cerr << "\033[32m[" << __LINE__ << "]\033[0m "
#define SZ(x) ((int) x.size() - 1)
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> T& chkmax(T& x, T y) {return x = max(x, y);}
template <typename T> T& chkmin(T& x, T y) {return x = min(x, y);}
template <typename T> T& read(T &x) {
	x = 0; int f = 1; char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
	return x *= f;
}
const int N = 1e5 + 10;
int n, a[N], q;
struct Node {
	bool flag;
	int ans;
	deque <pair <int, int>> tl, tr;
} info[N << 2];
int lg(int x) {return 31 ^ __builtin_clz(x);}
int calc(deque <pair <int, int>> x) {
	while (x.size() > 1) {
		if (x.front().first < x.back().first) {
			auto [a, b] = x.front(); x.erase(x.begin());
			a++, b /= 2;
			if (x.size() && x.front().first == a) x.front().second += b;
			else x.insert(x.begin(), make_pair(a, b));
		} else {
			auto [a, b] = x.back(); x.pop_back();
			a++, b /= 2;
			if (x.size() && x.back().first == a) x.back().second += b;
			else x.push_back(make_pair(a, b));
		}
	}
	return x.front().first + lg(x.front().second);
}
bool g;
deque <pair <int, int>> ta, tb, tc;
deque <pair <int, int>> rev(deque <pair <int, int>> x) {
	reverse(all(x));
	return x;
}
deque <pair <int, int>> dot(deque <pair <int, int>> x) {
	while (x.size() > 1 && x.back().first < x[SZ(x) - 1].first) {
		auto [a, b] = x.back(); x.pop_back();
		a++, b /= 2;
		if (x.size() && x.back().first == a) x.back().second += b;
		else x.push_back(make_pair(a, b));
	}
	return x;
}
bool work(deque <pair <int, int>> x, deque <pair <int, int>> y) {
	deque <pair <int, int>> ans;
	while (x.size() && y.size()) {
		if (x.back().first == y.front().first) {
			x.back().second += y.front().second;
			y.erase(y.begin());
		} else if (x.back().first < y.front().first) {
			if (x.size() == 1 || x[SZ(x) - 1].first < x.back().first) break;
			if (x.back().second & 1) {
				auto w = x.back();
				y.insert(y.begin(), w);
				ta = x, tb = y;
				// auto [a, b] = x.back(); x.pop_back();
				// a++, b /= 2;
				// if (x.size() && x.back().first == a) x.back().second += b;
				// else x.push_back(make_pair(a, b));
				return true;
			} else {
				auto [a, b] = x.back(); x.pop_back();
				a++, b /= 2;
				if (x.size() && x.back().first == a) x.back().second += b;
				else x.push_back(make_pair(a, b));
			}
		} else {
			if (y.size() == 1 || y[1].first < y.front().first) break;
			if (y.front().second & 1) {
				auto w = y.front();
				x.push_back(w);
				ta = x, tb = y;
				// auto [a, b] = x.back(); x.pop_back();
				// a++, b /= 2;
				// if (x.size() && x.back().first == a) x.back().second += b;
				// else x.push_back(make_pair(a, b));
				return true;
			} else {
				auto [a, b] = y.front(); y.erase(y.begin());
				a++, b /= 2;
				if (y.size() && y.front().first == a) y.front().second += b;
				else y.insert(y.begin(), make_pair(a, b));
			}
		}
	}
	ta = x, tb = y;
	return false;
}
Node operator + (Node x, Node y) {
	Node z;
	z.ans = max(x.ans, y.ans);
	if (x.flag && y.flag) {
		z.flag = true;
		z.tl = x.tl, z.tr = y.tr;
		// deque <pair <int, int>> tt;
		// reverse(all(x.tr));
		// for (auto i: x.tr) tt.push_back(i);
		// for (auto i: y.tl) tt.push_back(i);
		if (work(x.tr, y.tl)) {
			chkmax(z.ans, calc(ta));
			chkmax(z.ans, calc(tb));
		} else {
			deque <pair <int, int>> tt = ta;
			for (auto i: tb) tt.push_back(i);
			chkmax(z.ans, calc(tt));
		}
		// chkmax(z.ans, calc(tt));
	}
	if (x.flag && !y.flag) {
		z.flag = true;
		z.tl = x.tl;
		if (work(x.tr, y.tl)) {
			chkmax(z.ans, calc(ta));
			z.tr = rev(dot(rev(tb)));
		} else {
			z.tr = ta;
			for (auto i: tb) z.tr.push_back(i);
			z.tr = rev(dot(rev(z.tr)));
		}
	}
	if (!x.flag && y.flag) {
		z.flag = true;
		z.tr = y.tr;
		if (work(x.tl, y.tl)) {
			chkmax(z.ans, calc(tb));
			z.tl = dot(ta);
		} else {
			z.tl = ta;
			for (auto i: tb) z.tl.push_back(i);
			z.tl = dot(z.tl);
		}
	}
	if (!x.flag && !y.flag) {
		if (work(x.tl, y.tl)) {
			z.flag = true;
			z.tl = dot(ta);
			// reverse(all(tb));
			z.tr = rev(dot(rev(tb)));
		} else {
			z.flag = false;
			z.tl = ta;
			for (auto i: tb) z.tl.push_back(i);
		}
	}
	return z;
}
void pushup(int num) {
	// debug << "~ " << (ls) << " " << (rs) << endl;
	info[num] = info[ls] + info[rs];
}
void init(int num, int x) {
	info[num].flag = false;
	info[num].ans = a[x];
	info[num].tl.clear();
	info[num].tr.clear();
	info[num].tl.emplace_back(a[x], 1);
}
void build(int num, int l, int r) {
	if (l == r) {
		init(num, l);
		return;
	}
	build(li), build(ri);
	pushup(num);
}
void modify(int num, int l, int r, int x) {
	if (l == r) {
		init(num, l);
		return;
	}
	if (mid >= x) modify(li, x);
	else modify(ri, x);
	pushup(num);
}
Node query(int num, int l, int r, int L, int R) {
	if (L <= l && r <= R) return info[num];
	if (mid >= R) return query(li, L, R);
	if (mid < L) return query(ri, L, R);
	return query(li, L, R) + query(ri, L, R);
}
void prepare_game(vector<int>A) {
	n = A.size();
	F(i, 1, n) a[i] = A[i - 1];
	build(1, 1, n);
}
int play_game(int x, int y) {
	x++;
	Node w = query(1, 1, n, x, y);
	chkmax(w.ans, calc(w.tl));
	if (w.flag) chkmax(w.ans, calc(w.tr));
	return w.ans;
}
void update_game(int x, int y) {
	x++, y++;
	a[x] = y;
	modify(1, 1, n, x);
}
// signed main() {
// 	// freopen("seq.in", "r", stdin);
// 	// freopen("seq.out", "w", stdout);
// 	// return 0;
// 	read(q);
// 	while (q--) {
// 		int op, x, y; read(op), read(x), read(y);
// 		if (op == 2) {
// 			a[x] = y;
// 			modify(1, 1, n, x);
// 		} else {
// 			Node w = query(1, 1, n, x, y);
// 			chkmax(w.ans, calc(w.tl));
// 			if (w.flag) chkmax(w.ans, calc(w.tr));
// 			cout << w.ans << '\n';
// 		}
// 	}
// 	return 0;
// }
// /* why?
// */
Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 25700kb

input:

10
2 2 1 2 2 2 2 1 2 2
10
1 0 2
1 0 9
1 0 5
1 2 4
1 0 9
1 2 7
1 3 7
1 7 9
1 1 3
1 0 2

output:

3
4
3
2
4
4
4
2
2
3

result:

wrong answer 4th lines differ - expected: '3', found: '2'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #31:

score: 0
Wrong Answer
time: 14ms
memory: 26044kb

input:

4000
1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 2 2 2 1 1 1 1 2 2 2 2...

output:

11
12
12
11
10
11
10
11
12
10
9
10
9
9
9
11
11
10
10
9
11
8
9
10
11
11
10
11
10
8
9
10
9
10
10
10
10
10
9
7
5
10
8
10
10
7
10
10
6
10
10
10
10
9
9
10
10
10
7
6
10
10
10
10
9
10
8
10
10
10
10
10
10
9
8
10
10
10
10
9
10
10
7
10
9
9
7
9
10
10
8
8
10
10
8
10
9
6
7
9
9
10
9
7
10
10
9
10
9
10
9
8
10
10
9
...

result:

wrong answer 16th lines differ - expected: '12', found: '11'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #3:

0%

Subtask #6:

score: 0
Wrong Answer

Test #69:

score: 0
Wrong Answer
time: 459ms
memory: 34440kb

input:

100000
2 10 6 3 5 4 2 6 9 3 8 3 9 6 9 8 8 9 4 6 5 10 7 1 2 5 5 2 7 3 5 10 5 6 7 5 9 10 6 10 7 3 2 1 7 8 4 4 3 10 1 6 9 9 6 9 6 1 6 4 8 5 5 6 8 3 3 7 6 6 3 5 5 9 5 5 7 10 7 3 10 1 4 2 3 6 9 2 7 2 8 10 4 5 2 6 7 1 8 2 8 3 3 10 9 8 6 6 9 6 4 5 8 4 10 10 4 1 6 4 4 3 9 4 7 7 2 8 8 7 10 6 8 2 1 4 2 2 5 2 ...

output:

12
11
11
12
12
12
11
12
12
12
12
12
11
12
12
12
12
12
12
12
12
12
12
12
12
11
12
12
11
10
12
12
12
12
12
12
12
12
12
12
12
12
12
11
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
11
12
12
12
12
11
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
12
11
12
12
12
12
12
12
12
12
12
12
12
...

result:

wrong answer 15288th lines differ - expected: '5', found: '4'

Subtask #7:

score: 0
Skipped

Dependency #1:

0%
English 繁體中文 简体中文

Server Time: 2024-12-03 23:24:30 | OpenSource Project