//#define TEST
#ifndef TEST
#include "teams.h"
#endif // TEST
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int len = 5e5+5;
vector<int> stud[len];
int team[len], n, dp[len], pre[len], nex[len], in[len];
priority_queue<ii, vector<ii>, greater<ii> > pq;
struct node{
int sum;
node *left, *right;
node(int s = 0, node *l = NULL, node *r = NULL){
sum = s;
left = l;
right = r;
}
};
typedef node* pnode;
pnode null = new node(), root[len];
pnode update(pnode t, int l, int r, int i){
if (l == r)
return new node(t->sum+1, null, null);
int mid = (l+r)/2;
if (i <= mid)
return new node(t->sum+1, update(t->left, l, mid, i), t->right);
return new node(t->sum+1, t->left, update(t->right, mid+1, r, i));
}
int ask(pnode a, pnode b, int l, int r, int i, int j){
if (r < i || j < l || i > j)
return 0;
if (i <= l && r <= j)
return (a->sum-b->sum);
int mid = (l+r)/2;
return ask(a->left, b->left, l, mid, i, j) + ask(a->right, b->right, mid+1, r, i, j);
}
int query(pnode a, pnode b, int l, int r, int x){
//printf("l = %d, r = %d, x = %d\n", l, r, x);
if (l == r){
if ((a->sum-b->sum) <= x)
return l;
return l+1;
}
int mid = (l+r)/2, rig = (a->right->sum-b->right->sum);
if (rig <= x)
return query(a->left, b->left, l, mid, x-rig);
return query(a->right, b->right, mid+1, r, x);
}
void init(int N, int A[], int B[]){
n = N;
for (int i = 1; i <= n; i++)
stud[i].clear();
for (int i = 0; i < n; i++)
stud[A[i]].pb(B[i]);
//for (int i = 0; i < n; i++)
// printf("student: %d - %d\n", A[i], B[i]);
root[0] = null->left = null->right = null;
for (int i = 1; i <= n; i++){
root[i] = root[i-1];
for (int j = 0; j < stud[i].size(); j++)
root[i] = update(root[i], 1, n, stud[i][j]);
}
}
int can(int m, int K[]){
for (int i = 1; i <= m; i++)
team[i] = K[i-1];
sort(team+1, team+m+1);
int sum = 0;
for (int i = 1; i <= m; i++)
sum = min(n+1, team[i]+sum);
if (sum > n)
return 0;
/*printf("team =\n");
for (int i = 1; i <= m; i++)
printf("%d ", team[i]);
printf("\n");*/
while (!pq.empty())
pq.pop();
for (int i = 0; i <= m; i++){
in[i] = 0;
pre[i] = -1;
nex[i] = -1;
}
in[0] = 1, pre[0] = -1, nex[0] = -1;
int ans = 1, opt = 0;
for (int i = 1; i <= m; i++){
while (!pq.empty() && pq.top().fi <= team[i]){
ii cur = pq.top();
pq.pop();
if (!in[cur.se]) continue;
in[cur.se] = 0;
int pr = pre[cur.se], ne = nex[cur.se];
nex[pr] = ne;
if (ne == -1){
opt = pr;
}
else{
pre[ne] = pr;
//printf("%d with %d: %d\n", pr, ne, query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]));
pq.push(mp(query(root[team[ne]], root[team[pr]], 1, n, dp[ne]-dp[pr]), ne));
}
}
int tim = query(root[team[i-1]], root[team[opt]], 1, n, dp[i-1]-dp[opt]);
//printf("%d with %d: %d\n", opt, i-1, tim);
if (i != 1 && tim > team[i]){
in[i-1] = 1;
nex[opt] = i-1;
pre[i-1] = opt;
nex[i-1] = -1;
opt = i-1;
pq.push(mp(tim, opt));
}
//printf("i = %d, team = %d, opt = %d\n", i, team[i], opt);
dp[i] = dp[opt]+ask(root[team[i]], root[team[opt]], 1, n, team[i], n)-team[i];
//printf("i = %d, dp = %d\n", i, dp[i]);
//printf("i = %d, opt = %d, dp = %d\n", i, opt, dp[i]);
/*printf("all opts:");
for (int j = opt; j != -1; j = pre[j])
printf(" %d", j);
printf("\n");*/
if (dp[i] < 0)
ans = 0;
}
//printf("ans = %d\n", ans);
return ans;
}
#ifdef TEST
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;
static inline int _read() {
if (_charsNumber < 0) {
exit(1);
}
if (!_charsNumber || _currentChar == _charsNumber) {
_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
_currentChar = 0;
}
if (_charsNumber <= 0) {
return -1;
}
return _buffer[_currentChar++];
}
static inline int _readInt() {
int c, x, s;
c = _read();
while (c <= 32) c = _read();
x = 0;
s = 1;
if (c == '-') {
s = -1;
c = _read();
}
while (c > 32) {
x *= 10;
x += c - '0';
c = _read();
}
if (s < 0) x = -x;
return x;
}
int main() {
for (int t = 1; t <= 30; t++){
char test[10];
if (t < 10)
sprintf(test, "0%d", t);
else
sprintf(test, "%d", t);
printf("test file %s\n", test);
_inputFile = fopen(test, "rb");
//_outputFile = fopen("teams2.out", "w");
int N;
N = _readInt();
int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
for (int i = 0; i < N; ++i) {
A[i] = _readInt();
B[i] = _readInt();
}
if (N <= 1000)
init(N, A, B);
printf("N = %d\n", N);
//vector<int> hel;
//hel.clear();
int Q;
Q = _readInt();
//Q = 1;
printf("Q = %d\n", Q);
for (int i = 0; i < Q; ++i) {
//printf("quere number %d\n", i);
int M;
M = _readInt();
//printf("M = %d\n", M);
int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
for (int j = 0; j < M; ++j) {
K[j] = _readInt();
}
/*printf("M = %d\n", M);
for (int j = 0; j < M; j++)
printf("%d ", K[j]);
printf("\n");*/
if (N <= 1000){
//hel.pb(can(M, K));
fprintf(_outputFile,"%d\n", can(M, K));
}
}
/*if (0){
if (t < 10)
sprintf(test, "0%d.a", t);
else
sprintf(test, "%d.a", t);
_inputFile = fopen(test, "rb");
for (int i = 0; i < Q; i++){
int cor = _readInt();
if (cor != hel[i])
printf("my answer = %d, correct = %d\n", hel[i], cor);
}
}*/
}
return 0;
}
#endif // TEST
