| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 348845 | dennisstar | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
const int MX = 5e5 + 5;
vector<int> st[1<<20];
void upd(int i, int s, int e, int t, int v) {
st[i].eb(v);
if (s==e) return ;
int m=(s+e)/2;
if (t<=m) upd(i*2, s, m, t, v);
else upd(i*2+1, m+1, e, t, v);
}
void init(int i, int s, int e) {
sort(st[i].begin(), st[i].end());
if (s==e) return ;
int m=(s+e)/2;
init(i*2, s, m); init(i*2+1, m+1, e);
}
struct {
int used;
int l, r;
}nd[1<<23];
int nc;
int use(int n, int i, int s, int e, int w, int v) {
int t=upper_bound(st[i].begin(), st[i].end(), w)-st[i].begin();
if (t-nd[n].used<=v) {
int r=t-nd[n].used;
nd[n].used=t;
return r;
}
if (s==e) {
nd[n].used+=v;
return v;
}
int m=(s+e)/2;
if (!nd[n].l) {
assert(nd[n].used==0);
nd[n].l=++nc;
nd[n].r=++nc;
}
int x=use(nd[n].l, i*2, s, m, w, v);
int y=(x==v?0:use(nd[n].r, i*2+1, m+1, e, w, v-x));
nd[n].used=nd[nd[n].l].used+nd[nd[n].r].used;
return x+y;
}
void kill(int n, int i, int s, int e, int t) {
if (t<s) return ;
if (e<=t) { nd[n].used=st[i].size(); return ; }
int m=(s+e)/2;
if (!nd[n].l) {
nd[n].l=++nc;
nd[n].r=++nc;
}
kill(nd[n].l, i*2, s, m, t);
kill(nd[n].r, i*2+1, m+1, e, t);
nd[n].used=nd[nd[n].l].used+nd[nd[n].r].used;
}
int N, Q;
int sol() {
int M;
cin>>M;
vector<int> K(M);
for (auto &i:K) cin>>i;
sort(K.begin(), K.end());
int rt=++nc;
for (auto &i:K) {
kill(rt, 1, 1, N, i-1);
if (use(rt, 1, 1, N, i, i)<i) return 0;
}
return 1;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>>N;
for (int i=1, a, b; i<=N; i++) cin>>a>>b, upd(1, 1, N, b, a);
init(1, 1, N);
cin>>Q;
while (Q--) cout<<sol()<<'\n';
return 0;
}