| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 559823 | emuyumi | Teams (IOI15_teams) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Segtree{
#define mid ((l + r) >> 1)
struct Node{
int lc, rc, val;
};
int N;
vector<Node> st;
int T;
Segtree() = default;
Segtree(int N) : N(N) {
st.resize(25 * N);
T = 0;
build(0, 1, N);
}
int build(int v, int l, int r){
if (l == r) return v;
st[v].lc = build(++T, l, mid);
st[v].rc = build(++T, mid + 1, r);
return v;
}
int insert(int v, int l, int r, int idx){
int nv = ++T;
if (l == r){
st[nv] = {0, 0, st[v].val + 1};
}
else if (idx <= mid){
st[nv].lc = insert(st[v].lc, l, mid, idx);
st[nv].rc = st[v].rc;
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
else{
st[nv].lc = st[v].lc;
st[nv].rc = insert(st[v].rc, mid + 1, r, idx);
st[nv].val = st[st[nv].lc].val + st[st[nv].rc].val;
}
return nv;
}
int insert(int v, int idx){ return insert(v, 1, N, idx); }
int query(int vl, int vr, int l, int r, int ql, int qr){
if (l > qr || r < ql || ql > qr) return 0;
if (l >= ql && r <= qr) return st[vr].val - st[vl].val;
return query(st[vl].lc, st[vr].lc, l, mid, ql, qr) +
query(st[vl].rc, st[vr].rc, mid + 1, r, ql, qr);
}
int query(int vl, int vr, int ql, int qr){ return query(vl, vr, 1, N, ql, qr); }
#undef mid
};
using pii = pair<int, int>;
Segtree st;
vector<int> rts;
int N;
vector<pii> xs, ys;
void init(int N, int A[], int B[]){
::N = N;
for (int i = 0; i < N; ++i){
xs.push_back({A[i], i});
ys.push_back({B[i], i});
}
// give each point unique x and unique y
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
vector<int> y(N + 1);
for (int i = 0; i < N; ++i){
int x = lower_bound(xs.begin(), xs.end(), pii{A[i], i}) - xs.begin() + 1;
y[x] = lower_bound(ys.begin(), ys.end(), pii{B[i], i}) - ys.begin() + 1;
// cerr << x << " " << y[x] << '\n';
}
st = Segtree(N + 1);
rts.resize(N + 1);
int v = 0;
for (int x = 1; x <= N; ++x){
v = st.insert(v, y[x]);
rts[x] = v;
}
}
// number of points in [x1, x2] x [y1, y2]
int count(int x1, int x2, int y1, int y2){
x2 = min(x2, N);
y2 = min(y2, N);
return st.query(rts[x1 - 1], rts[x2], y1, y2);
}
int can(int M, int K[]){
sort(K, K + M);
struct Point{ int x, y; };
vector<Point> stk = {};
stk.push_back({0, N + 1});
for (int i = 0; i < M; ++i){
int qx = upper_bound(xs.begin(), xs.end(), pii{K[i], 1e9}) - xs.begin() + 1 - 1;
int qy = lower_bound(ys.begin(), ys.end(), pii{K[i], -1}) - ys.begin() + 1;
while (stk.back().y < qy){
stk.pop_back();
}
int need = K[i];
while (need){
if (stk.empty()){
return 0;
}
auto [lx, ly] = stk.back();
/*
**........^
**........^
*****%%%%%% ly
*****%%%%%% qy
***********
***********
lx qx
*/
int rect = count(lx + 1, qx, qy, ly);
// cerr << lx + 1 << " " << qx << " " << qy << " " << ly << '\n';
// cerr << rect << '\n';
if (rect <= need){
need -= rect;
qy = ly + 1;
stk.pop_back();
}
else{
// bsearch for new y
int lo = qy - 1, hi = ly;
while (lo < hi){
int mi = (lo + hi) >> 1;
int cnt = count(lx + 1, qx, qy, mi);
if (cnt >= need) hi = mi;
else lo = mi + 1;
}
need = 0;
qy = lo + 1;
}
}
stk.push_back({qx, qy - 1});
}
return 1;
}
const int MN = 5e5;
int A[MN], B[MN], K[MN];
int main(){
#ifdef ONLINE_JUDGE
cin.tie(0)->sync_with_stdio(0);
#endif
#ifndef ONLINE_JUDGE
freopen("txt.in", "r", stdin);
freopen("txt.out", "w", stdout);
#endif
int N; cin >> N;
for (int i = 0; i < N; ++i){
cin >> A[i] >> B[i];
}
init(N, A, B);
int Q; cin >> Q;
while (Q--){
int M; cin >> M;
for (int i = 0; i < M; ++i){
cin >> K[i];
}
cout << can(M, K) << '\n';
// int x1, x2, y1, y2;
// cin >> x1 >> x2 >> y1 >> y2;
// cout << count(x1, x2, y1, y2) << '\n';
}
}