#include "bits/stdc++.h"
#define ll long long
using namespace std;
struct STree {
vector<int> st, lz;
int sz, n;
STree(int N): sz(4 * N + 100), n(N) {
st.assign(sz, 0);
lz.assign(sz, 0);
}
void relax(int v) {
st[v] += lz[v];
if (v * 2 < sz)
lz[v * 2] += lz[v];
if (v * 2 + 1 < sz)
lz[v * 2 + 1] += lz[v];
lz[v] = 0;
}
void upd(int lo, int hi, int ix, int v, int k) {
if (lo > ix) return;
relax(v);
if (hi <= ix) {
lz[v] += k;
relax(v);
} else {
int mi = (lo + hi) / 2;
upd(lo, mi, ix, v * 2, k);
upd(mi + 1, hi, ix, v * 2 + 1, k);
st[v] = min(st[v * 2], st[v * 2 + 1]);
}
}
int qry() {
relax(1);
return st[1];
}
};
int main() {
int n;
cin >> n;
STree le(n), ri(n);
for (int i = 0; i < n; i ++) {
int a, b;
cin >> a >> b;
if (1 == b) {
le.upd(1, n, a, 1, -1);
ri.upd(1, n, a, 1, 1);
} else {
le.upd(1, n, a, 1, 1);
ri.upd(1, n, a, 1, -1);
}
int lq = le.qry(), rq = ri.qry();
if (0 > lq && rq >= 0)
cout << ">\n";
else if (0 > rq && lq >= 0)
cout << "<\n";
else cout << "?\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
