#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
struct SegTree {
int n;
vector <int> mx;
vector <int> mn;
vector <int> lazy;
SegTree (int n) {
this->n = n;
mx.resize (1 + 4 * n);
mn.resize (1 + 4 * n);
lazy.resize (1 + 4 * n);
}
void push (int node) {
int l = node * 2, r = node * 2 + 1;
mn[l] += lazy[node];
mx[l] += lazy[node];
mn[r] += lazy[node];
mx[r] += lazy[node];
lazy[l] += lazy[node];
lazy[r] += lazy[node];
}
void update (int node, int lb, int rb, int x, int y, int val) {
if (x <= lb && rb <= y) {
mn[node] += val;
mx[node] += val;
lazy[node] += val;
return;
}
int mid = (lb + rb) / 2, lNode = node * 2, rNode = node * 2 + 1;
push (node);
if (x <= mid)
update (lNode, lb, mid, x, y, val);
if (mid + 1 <= y)
update (rNode, mid + 1, rb, x, y, val);
mn[node] = min (mn[lNode], mn[rNode]);
mx[node] = max (mx[lNode], mx[rNode]);
}
char query () { /// 1 means >, -1 means <, and 0 means ?
if (mn[1] >= 0)
return '>';
if (mx[1] <= 0)
return '<';
return '?';
}
};
int main () {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
cin >> n;
SegTree seg (n);
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
seg.update (1, 1, n, 1, x, (y == 1) ? 1 : -1);
cout << seg.query () << "\n";
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
