Submission #87046

#	Time	Username	Problem	Language	Result	Execution time	Memory
87046		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];

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	ll sum1, sum2;
	sum1 = sum2 = 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) {
			sum1 += r;
		} else {
			sum2 += r;
		}
		tr[s].upd(r, 1);
	}
	vector < char > ans;
	for (int i = n; i >= 1; i--) {
		int res1, res2;
		res1 = tr[1].get(1, n);
		res2 = tr[2].get(1, n);
		if (res1 == res2) {
			if (sum1 > sum2) {
				ans.push_back('>');
			} else if (sum1 < sum2) {
				ans.push_back('<');
			} else {
				ans.push_back('?');
			}
		} else if (res1 < res2) {
			if (sum1 >= sum2) {
				ans.push_back('?');
			} else {
				ans.push_back('<');
			}
		} else {
			if (sum1 <= sum2) {
				ans.push_back('?');
			} else {
				ans.push_back('>');
			}
		}
		tr[S[i]].upd(R[i], -1);
		if (S[i] == 1) {
			sum1 -= R[i];
		} else {
			sum2 -= 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

*/

Compilation message (stderr)

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

• Subtask 1: 0 / 100