| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 563023 | HunterXD | 팀들 (IOI15_teams) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define f first
#define s second
#define pb push_back
vector<ll> power = {1};
ll val_power = 25;
struct ST{
ll l, r;
ST *left = NULL, *right = NULL;
vector<ll> arr, sum;
ll arr_size = 0;
ll marked = -1, lazy_marked = -1;
bool reset = false;
ST(ll l, ll r, vector< vector<ll> > *ar){
this->l = l; this->r = r;
if(l == r){
arr = (*ar)[l];
arr_size = arr.size();
sum.assign(arr_size, 0);
sort(arr.begin(), arr.end(), greater<ll>());
return;
}
ll med = (l+r)/2;
left = new ST(l, med, ar);
right = new ST(med+1, r, ar);
arr_size = left->arr_size + right->arr_size;
sum.assign(arr_size, 0);
ll next = 0;
vector<ll>::iterator it_l = left->arr.begin(), it_r = right->arr.begin();
while(it_l != left->arr.end() && it_r != right->arr.end()){
if(*it_l > *it_r){
arr.pb(*(it_l++));
if(next) sum[next] = sum[next-1]+1;
else sum[next] = 1;
}
else{
arr.pb(*(it_r++));
if(next) sum[next] = sum[next-1];
else sum[next] = 0;
}
next++;
}
while(it_l != left->arr.end()){
arr.pb(*(it_l++));
if(next) sum[next] = sum[next-1]+1;
else sum[next] = 1;
next++;
}
while(it_r != right->arr.end()){
arr.pb(*(it_r++));
if(next) sum[next] = sum[next-1];
else sum[next] = 0;
next++;
}
}
ll next_marked(ll k){
ll next = marked+1;
for(ll i = val_power; i >= 0; i--){
if(next+power[i] >= arr_size) continue;
if(arr[next+power[i]] >= k) next = next+power[i];
}
return next;
}
void apply_lazy_stuff(){
if(l == r){
if(reset){
marked = -1;
lazy_marked = -1;
reset = false;
}
if(lazy_marked != -1){
marked = lazy_marked;
lazy_marked = -1;
}
return;
}
if(reset){
left->reset = true;
right->reset = true;
marked = -1;
lazy_marked = -1;
reset = false;
}
if(lazy_marked != -1){
marked = lazy_marked;
left->lazy_marked = -1+sum[marked];
right->lazy_marked = -1+(marked+1-sum[marked]);
lazy_marked = -1;
}
}
ll mark(ll s_l, ll s_r, ll i, ll k){
apply_lazy_stuff();
//si está fuera del rango
if(r < s_l || s_r < l) return 0;
//si no tiene elementos
if(marked+1 == arr_size) return 0;
//si no hay elementos libres mayores o igual a i
if(arr[marked+1] < i) return 0;
//si está adentro del rango
if( s_l <= l && r <= s_r ){
if(l != r){
left->apply_lazy_stuff();
right->apply_lazy_stuff();
}
lazy_marked = min(next_marked(i), marked+k);
return lazy_marked-marked;
}
//si alguna parte está afuera, vemos los dos, con prioridad en right
ll r1 = right->mark(s_l, s_r, i, k);
ll r2 = left->mark(s_l, s_r, i, k-r1);
return r1+r2;
}
};
ST *me = NULL;
ll on = 0;
vector< vector<ll> > my;
void init(ll n, ll a[], ll b[]) {
for(ll i = 1; i <= val_power; i++){
power.pb(2*power[i-1]);
}
on = n;
my.assign(n+1, vector<ll>());
for(ll i = 0; i < n; i++){
my[a[i]].pb(b[i]);
}
me = new ST(1, n, &my);
}
ll can(ll m, ll k[]) {
me = new ST(1, on, &my);
sort(k, k+m, greater<ll>());
ll v,t;
for(ll i = 0; i < m; i++){
v = k[i];
t = me->mark(1, v, v, v);
if(t != v){
return false;
}
}
return true;
}
int main(){
ll n;
cin >> n;
ll a[n], b[n];
for(ll i = 0; i < n; i++){
cin >> a[i] >> b[i];
}
init(n, a, b);
ll q;
cin >> q;
for(ll i = 0; i < q; i++){
ll t;
cin >> t;
ll k[t];
for(ll j = 0; j < t; j++) cin >> k[j];
cout << can(t, k) << endl;
}
}