| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 42220 | yusufake | Teams (IOI15_teams) | C++98 | 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;
#define _ int v, int tl, int tr, int l, int r
#define tm (tl + tr >> 1)
#define sol L[v],tl,tm,l,r
#define sag R[v],tm+1,tr,l,r
#define mp make_pair
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
pp A[N];
int root[N],T[N],n,q,m,i,x,kalan;
int s[N*18],L[N*18],R[N*18],id,p;
int up(_){
if(tl > r || tr < l) return v;
int nw = ++id;
if(tl == tr) { s[nw] = s[v] + 1; return nw; }
L[nw] = up(sol);
R[nw] = up(sag);
s[nw] = s[v] + 1;
return nw;
}
int qry(_) {
if(tl > r || tr < l) return 0;
if(tl >= l && tr <= r) return s[v];
return qry(sol) + qry(sag);
}
int main(){
freopen("input.in", "r", stdin);freopen("input.out", "w", stdout);
cin >> n;
for(i=1;i<=n;i++) cin >> A[i].st >> A[i].nd;
sort(A+1 , A+n+1);
for(i=1;i<=n;i++){
p = up(p,1,n,A[i].nd,A[i].nd);
if(A[i].st != A[i+1].st)
root[ A[i].st ] = p;
}
for(i=1;i<=n;i++)
if(!root[i])
root[i] = root[i-1];
for(cin >> q; q-- ;){
cin >> m;
for(i=1;i<=m;i++)
cin >> T[i];
sort(T+1 , T+m+1);
for(kalan=0,i=1;i<=m;i++){
x = T[i];
p = T[i-1];
kalan = min(kalan , qry(root[p],1,n,x,n));
kalan += qry(root[x],1,n,x,n) - qry(root[p],1,n,x,n);
//cout << qry(root[x],1,n,x,n) << " " << qry(root[p],1,n,x,n) << " aa\n";
kalan -= x;
//cout << kalan << " ss\n";
if(kalan < 0) break;
}
puts(i > m ? "1" : "0");
//return 1;
}
return 0;
}