이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
struct node {
int lc, rc, cnt;
} st[1<<24];
const int mxN = 5e5+1;
int n, ncnt = 1, rts[mxN];
int upd(int x, int t, int l, int r) {
if (t) st[ncnt] = st[t];
t = ncnt++;
st[t].cnt++;
if (r - l == 1) return t;
int m = l+r>>1;
if (x < m) st[t].lc = upd(x, st[t].lc, l, m);
else st[t].rc = upd(x, st[t].rc, m, r);
st[t].cnt = st[st[t].lc].cnt + st[st[t].rc].cnt;
return t;
}
int merge(int x, int t, int ot, int l, int r) {
if (!x) return ot;
if (st[t].cnt - st[ot].cnt <= x) return t;
int nt = ncnt++;
if (r - l == 1) {
st[nt].cnt = x;
return nt;
}
int m = l+r>>1;
st[nt].lc = merge(x, st[t].lc, st[ot].lc, l, m);
st[nt].rc = merge(x, st[t].rc, st[ot].rc, m, r);
st[nt].cnt = st[st[nt].lc].cnt + st[st[nt].rc].cnt;
return nt;
}
int get_lt(int x, int t, int ot, int l, int r) {
if (x >= r) return st[t].cnt - st[ot].cnt;
if (x <= l) return 0;
int m = l+r>>1;
return get_lt(x, st[t].lc, st[ot].lc, l, m), get_lt(x, st[t].rc, st[ot].rc, m, r);
}
void init(int N, int A[], int B[]) {
n = N;
vector<pii> order;
for (int i = 0; i < N; ++i) {
order.push_back({A[i], B[i]});
}
sort(order.begin(), order.end());
int it = 0;
for (int i = 1; i <= N; ++i) {
rts[i] = rts[i-1];
while (it < N && order[it].first == i) {
rts[i] = upd(order[it].second, rts[i], 1, N+1);
it++;
}
}
}
int can(int M, int K[]) {
sort(K, K+M);
int rt = 0, pv = 0;
for (int i = 0; i < M; ++i) {
int x = K[i];
int f = get_lt(x, rts[x], rt, 1, n+1);
rt = merge(x+f, rts[x], rt, 1, n+1);
if (st[rt].cnt != x+f+pv) return 0;
pv = st[rt].cnt;
}
return 1;
}
컴파일 시 표준 에러 (stderr) 메시지
teams.cpp: In function 'int upd(int, int, int, int)':
teams.cpp:18:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
18 | int m = l+r>>1;
| ~^~
teams.cpp: In function 'int merge(int, int, int, int, int)':
teams.cpp:33:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int m = l+r>>1;
| ~^~
teams.cpp: In function 'int get_lt(int, int, int, int, int)':
teams.cpp:43:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int m = l+r>>1;
| ~^~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |