#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
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;
^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
1528 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
