Submission #87058

#	Time	Username	Problem	Language	Result	Execution time	Memory
87058		Just_Solve_The_Problem	Weighting stones (IZhO11_stones)	C++11	0 / 100	3 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 lss;

pair < int, int > get() {
	int l = 0;
	int r = n + 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		int res = tr[1].get(mid, n) + tr[2].get(mid, n);
		if (res) {
			l = mid;
		} else {
			r = mid;
		}
	}
	int last = a[l];
	lss = last;
	l = -1;
	r = n + 1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (tr[3 - last].get(mid, n) == 0) {
			r = mid;
		} else {
			l = mid;
		}
	}
	pair < int, int > ret;
	ret.first = ret.second = 0;
	if (last == 1) {
		ret.first = tr[last].get(r, n);
	} else {
		ret.second = tr[last].get(r, n);
	}
	int asd = l;
	//cout << asd << ' ';
	r = l;
	l = -1;
	while (r - l > 1) {
		int mid = (l + r) >> 1;
		if (tr[last].get(mid, asd) == 0) {
			r = mid;
		} else {
			l = mid;
		}
	}
	//cout << r << '\n';
	if (last == 1) {
		ret.second = tr[3 - last].get(r, n);
	} else {
		ret.first = tr[3 - last].get(r, n);
	}
	return ret;
}

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;
		if (s == 1) {
			cur1 += r;
		} else {
			cur2 += r;
		}
		tr[s].upd(r, 1);
	}
	vector < char > ans;
	for (int i = n; i >= 1; i--) {
		pair < int, int > asd = get();
		//cout << lss << endl;
		//cout << asd.first << ' ' << asd.second << '\n';
		if (lss == 1) {
			if (cur2 >= cur1 || asd.second > asd.first) {
				ans.push_back('?');
			} else {
				ans.push_back('>');
			}
		} else {
			if (cur1 >= cur2 || asd.first > asd.second) {
				ans.push_back('?');
			} else {
				ans.push_back('<');
			}
		}
		tr[S[i]].upd(R[i], -1);
		if (S[i] == 1) {
			cur1 -= R[i];
		} else {
			cur2 -= R[i];
		}
	}
	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


5
1 2
2 2
3 1
4 1
5 2

5
5 1
4 1
1 2
2 2
3 2

6
5 1
4 1
1 2
2 2
3 2
6 2
*/

Compilation message (stderr)

stones.cpp:91:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
stones.cpp: In function 'int main()':
stones.cpp:98:6: warning: unused variable 'last' [-Wunused-variable]
  int last = -1;
      ^~~~

• Subtask 1: 0 / 100