#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;
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 += (n - r);
} else {
sum2 += (n - r);
}
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) {
if (sum1 >= sum2) {
ans.push_back('?');
} else {
ans.push_back('>');
}
} else if (res1 > res2) {
ans.push_back('>');
} else {
ans.push_back('?');
}
} else {
if (res1 == res2) {
if (sum1 <= sum2) {
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);
if (S[i] == 1) {
sum1 -= (n - R[i]);
} else {
sum2 -= (n - 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
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:59: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 |
- |
