#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] , r , s;
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];
}
int x1 , x2;
set < int > v ;
set < int > :: iterator vi ;
set < int > q ;
set < int > :: iterator qi ;
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
if (n <= 1000 )
{
for (int i = 0 ;i < n ;i ++ )
{
x1 = 0 ;
x2 = 0 ;
cin >> r >> s ;
if (i == 0)
{
if (s == 1)
cout << '>' << endl ;
else
cout << '<' << endl ;
if (s == 1)
v.insert (r) ;
else
q.insert (r) ;
}
else
{
if (s == 1)
v.insert (r) ;
else
q.insert (r) ;
if (v.size() == 0)
cout << '<' << endl ;
else
if (q.size() == 0 )
cout << '>' << endl ;
else
{
qi = -- q.end();
for (vi = --v.end(); ; vi -- )
{
if ( (*vi) > (*qi))
x1 ++ ;
else
x2 ++ ;
if (qi == q.begin()|| vi == v.begin() || (x1 > 0 && x2 > 0) )
break;
qi -- ;
}
if (x1 > x2 && x2 == 0 && x1 == q.size())
cout << '>' << endl ;
else
if (x1 < x2 && x1 == 0 && x2 == v.size())
cout << '<' << endl;
else
cout << '?' << endl ;
}
}
}
exit(0) ;
}
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';
}
}
Compilation message
stones.cpp:55:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
stones.cpp: In function 'int main()':
stones.cpp:104:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x1 > x2 && x2 == 0 && x1 == q.size())
~~~^~~~~~~~~~~
stones.cpp:107:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (x1 < x2 && x1 == 0 && x2 == v.size())
~~~^~~~~~~~~~~
stones.cpp:118:6: warning: unused variable 'last' [-Wunused-variable]
int last = -1;
^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 2 |
Correct |
3 ms |
1528 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1560 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1620 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1636 KB |
Output is correct |
| 6 |
Correct |
4 ms |
1696 KB |
Output is correct |
| 7 |
Correct |
5 ms |
1696 KB |
Output is correct |
| 8 |
Incorrect |
4 ms |
1824 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
