#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
struct segt
{
struct node {
int a[4] = {0, 0, 0, 0};
} dat[400005];
node comb(node L, node R) {
node ret;
ret.a[0] = L.a[0] + R.a[0];
ret.a[1] = L.a[1] + R.a[1];
ret.a[2] = max(L.a[2] + R.a[0] - R.a[1], R.a[2]);
ret.a[3] = max(L.a[3] + R.a[1] - R.a[0], R.a[3]);
return ret;
}
void modify(int idx, int v, int cv = 1, int cl = 0, int cr = 100005) {
if(cl == cr) {
dat[cv].a[v] ++;
dat[cv].a[2] = max(0, dat[cv].a[0] - dat[cv].a[1]);
dat[cv].a[3] = max(0, dat[cv].a[1] - dat[cv].a[0]);
return;
}
int mid = cl + cr >> 1;
if(idx <= mid) modify(idx, v, cv << 1, cl, mid);
else modify(idx, v, cv << 1 | 1, mid + 1, cr);
dat[cv] = comb(dat[cv << 1], dat[cv << 1 | 1]);
}
node query(int ql, int qr, int cv = 1, int cl = 0, int cr = 100005) {
if(cl > qr || cr < ql || cl > cr) return node();
if(ql <= cl && cr <= qr) return dat[cv];
int mid = cl + cr >> 1;
return comb(query(ql, qr, cv << 1, cl, mid), query(ql, qr, cv << 1 | 1, mid + 1, cr));
}
} tre;
int main()
{
int n;
scanf("%d", &n);
set<PII> st;
rep(i, n) {
int r, s; scanf("%d%d", &r, &s); s --;
st.insert({r, s});
tre.modify(r, s);
int win = prev(st.end())->second;
if(tre.query(1, n).a[2 + 1 - win] > 0) puts("?");
else puts(win == 0 ? ">" : "<");
}
return 0;
}
Compilation message
stones.cpp: In member function 'void segt::modify(int, int, int, int, int)':
stones.cpp:30:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = cl + cr >> 1;
| ~~~^~~~
stones.cpp: In member function 'segt::node segt::query(int, int, int, int, int)':
stones.cpp:38:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
38 | int mid = cl + cr >> 1;
| ~~~^~~~
stones.cpp: In function 'int main()':
stones.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
stones.cpp:49:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
49 | int r, s; scanf("%d%d", &r, &s); s --;
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
320 KB |
Output is correct |
| 8 |
Correct |
1 ms |
468 KB |
Output is correct |
| 9 |
Correct |
2 ms |
340 KB |
Output is correct |
| 10 |
Correct |
8 ms |
1108 KB |
Output is correct |
| 11 |
Correct |
59 ms |
5748 KB |
Output is correct |
| 12 |
Correct |
95 ms |
9104 KB |
Output is correct |
| 13 |
Correct |
80 ms |
10016 KB |
Output is correct |
| 14 |
Correct |
90 ms |
10056 KB |
Output is correct |
| 15 |
Correct |
82 ms |
10052 KB |
Output is correct |
| 16 |
Correct |
84 ms |
10016 KB |
Output is correct |
| 17 |
Correct |
74 ms |
10060 KB |
Output is correct |
| 18 |
Correct |
73 ms |
9952 KB |
Output is correct |
| 19 |
Correct |
71 ms |
9948 KB |
Output is correct |
| 20 |
Correct |
72 ms |
10040 KB |
Output is correct |
| 21 |
Correct |
83 ms |
10036 KB |
Output is correct |
| 22 |
Correct |
78 ms |
10024 KB |
Output is correct |
| 23 |
Correct |
76 ms |
10068 KB |
Output is correct |
| 24 |
Correct |
91 ms |
10060 KB |
Output is correct |
| 25 |
Correct |
78 ms |
10016 KB |
Output is correct |
