Pagini recente » Cod sursa (job #1982952) | Cod sursa (job #3241374) | Cod sursa (job #3147069) | Cod sursa (job #2493432) | Cod sursa (job #1553872)
# include <bits/stdc++.h>
using namespace std;
int len[32005];
int v[32005];
int p[32005];
int *s[32005];
int cnt_v;
int a[16005],b[16005];
int go(int pos,int val)
{
int ans = 0;
for (int i = 1 << 15;i;i >>= 1)
if (ans + i <= len[pos] && s[pos][ans+i] <= val) ans += i;
return ans;
}
int bin(int val)
{
int ans = 0;
for (int i = 1 << 15;i;i >>= 1)
if (ans + i <= cnt_v && v[ans+i] <= val) ans += i;
if (ans <= cnt_v && v[ans] < val) ++ans;
return ans;
}
void update_len(int i,int val)
{
for (;i <= cnt_v;i += i&(-i)) p[i] += val;
}
int query_len(int i)
{
int ans = 0;
for (;i;i -= i&(-i)) ans += p[i];
return ans;
}
void update_arb(int i,int val)
{
for (;i <= cnt_v;i += i&(-i)) s[i][++len[i]] = val;
}
int query_arb(int i,int l,int r)
{
if (i<0) return 0;
int ans = 0;
for (;i;i -= i&(-i))
{
ans += go(i,r) - go(i,l-1);
}
return ans;
}
int main(void)
{
int n;
ifstream fi("zoo.in");
ofstream fo("zoo.out");
ios_base :: sync_with_stdio(0);
fi>>n;
for (int i = 1;i <= n;++i) fi>>a[i]>>b[i],v[++cnt_v] = a[i],v[++cnt_v] = b[i];
sort(v+1,v+1+cnt_v);
for (int i = 1;i <= n;++i) a[i] = bin(a[i]),b[i] = bin(b[i]),update_len(a[i],b[i]);
for (int i = 1;i <= cnt_v;++i) s[i] = new int[query_len(i) - query_len(i-1) + 5];
for (int i = 1;i <= n;++i) update_arb(a[i],b[i]);
for (int i = 1;i <= cnt_v;++i) sort(s[i]+1,s[i]+1+len[i]);
int q;
fi>>q;
while (q --)
{
int x1,x2,y1,y2;
fi>>x1>>y1>>x2>>y2;
x1 = bin(x1);y1 = bin(y1);x2 = bin(x2);y2 = bin(y2);
fo << query_arb(x2,y1,y2) - query_arb(x1-1,y1,y2) << '\n';
}
return 0;
}