Submission #87041

#	Time	Username	Problem	Language	Result	Execution time	Memory
87041		Just_Solve_The_Problem	Weighting stones (IZhO11_stones)	C++11	0 / 100	4 ms	1528 KiB

stones

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int N = (int)1e5 + 7;

struct fen {
	int tree[N];
	fen() {
		memset(tree, 0, sizeof tree);
	}
	void upd(int pos, int val) {
		while (pos < N) {
			tree[pos] += val;
			pos = pos | (pos + 1);
		}
	}
	int get(int r) {
		int res = 0;
		while (r >= 0) {
			res += tree[r];
			r = (r & (r + 1)) - 1;
		}
		return res;
	}
	int get(int l, int r) {
		return get(r) - get(l - 1);
	}
};
fen tr[3];

int n;
int a[N];
int R[N], S[N];

int get() {
	int l = 0;
	int r = n + 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (tr[1].get(mid, n) + tr[2].get(mid, n) == 0) {
			r = mid;
		} else {
			l = mid;
		}
	}
	return a[l];
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int cur1, cur2;
	cur1 = cur2 = 0;
	int last = -1;
	for (int i = 1; i <= n; i++) {
		int r, s;
		cin >> r >> s;
		a[r] = s;
		R[i] = r;
		S[i] = s;
		tr[s].upd(r, 1);
	}
	vector < char > ans;
	for (int i = n; i >= 1; i--) {
		int last = get();
		int res1, res2;
		res1 = tr[1].get(1, n);
		res2 = tr[2].get(1, n);
		if (last == 1) {
			if (res1 >= res2) {
				ans.push_back('>');
			} else {
				ans.push_back('?');
			}
		} else {
			if (res1 <= res2) {
				ans.push_back('<');
			} else {
				ans.push_back('?');
			}
		}
		tr[S[i]].upd(R[i], -1);
	}
	reverse(ans.begin(), ans.end());
	for (char to : ans) {
		cout << to << '\n';
	}
}
/*
7
1 1
2 2
3 1
4 2
6 1
5 2
7 1

*/

Compilation message (stderr)

stones.cpp:52:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
stones.cpp: In function 'int main()':
stones.cpp:57:6: warning: variable 'cur1' set but not used [-Wunused-but-set-variable]
  int cur1, cur2;
      ^~~~
stones.cpp:59:6: warning: unused variable 'last' [-Wunused-variable]
  int last = -1;
      ^~~~

• Subtask 1: 0 / 100