Pagini recente » Cod sursa (job #1242719) | Cod sursa (job #1296319) | Cod sursa (job #1664024) | Cod sursa (job #2837558) | Cod sursa (job #1553898)
# 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 ok)
{
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 && !ok) ++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)
{
set < int > w;
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],w.insert(a[i]),w.insert(b[i]);
for (auto it : w) v[++cnt_v] = it;
for (int i = 1;i <= n;++i) a[i] = bin(a[i],0),b[i] = bin(b[i],0),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,0);y1 = bin(y1,0);x2 = bin(x2,1);y2 = bin(y2,1);
if (x1 <= x2 && y1 <= y2 && x2 <= cnt_v && y2 <= cnt_v) fo << query_arb(x2,y1,y2) - query_arb(x1-1,y1,y2) << '\n';
else fo << "0\n";
}
return 0;
}