Pagini recente » Monitorul de evaluare | Cod sursa (job #2019544) | Cod sursa (job #2843569) | Cod sursa (job #2952392) | Cod sursa (job #2752964)
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <climits>
using namespace std;
/// solutie cu aib si sortarea intervalelor dupa evenimente
const int NMAX = 16000;
const int MMAX = 100000;
vector<pair<int, int>> v;
vector<int> coordX;
int n;
int aib[1 + NMAX];
inline bool comp(pair<int, int>& a, pair<int, int>& b)
{
return a.second < b.second;
}
struct Event
{
int id;
int tip; /// 1 pentru deschidere de interval, 0 pt inchidere
int y;
int st;
int dr;
Event() {};
Event(int id, int tip, int y, int st, int dr) :
id(id), tip(tip), y(y), st(st), dr(dr) {};
bool operator <(const Event& other) const
{
return this->y < other.y;
}
};
void update(int pos, int val)
{
for (; pos <= n; pos += pos & -pos)
aib[pos] += val;
}
int query(int pos)
{
int sol = 0;
for (; pos > 0; pos -= pos & -pos)
sol += aib[pos];
return sol;
}
vector<Event> events;
int sol[1 + MMAX];
int main()
{
ifstream in("zoo.in");
ofstream out("zoo.out");
in >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
in >> x >> y;
v.emplace_back(x, y);
}
sort(v.begin(), v.end());
int lastX = -2000000001;
coordX.emplace_back(lastX);
for (int i = 0; i < v.size(); i++)
{
if (v[i].first > lastX)
{
lastX = v[i].first;
coordX.emplace_back(v[i].first);
}
v[i].first = coordX.size() - 1;
}
sort(v.begin(), v.end(), comp);
int m;
in >> m;
for (int j = 1; j <= m; j++)
{
int x1, y1, x2, y2;
in >> x1 >> y1 >> x2 >> y2;
events.emplace_back(j, 1, y1 - 1, x1, x2);
events.emplace_back(j, 0, y2, x1, x2);
}
sort(events.begin(), events.end());
int idx = 0;
for (int j = 0; j < events.size(); j++)
{
while (idx < v.size() && v[idx].second <= events[j].y)
{
update(v[idx].first, 1);
idx++;
}
int idx1 = lower_bound(coordX.begin(), coordX.end(), events[j].st) - coordX.begin();
int idx2 = upper_bound(coordX.begin(), coordX.end(), events[j].dr) - coordX.begin() - 1;
if (idx2 == -1) continue;
if (events[j].tip == 1)
sol[events[j].id] -= query(idx2) - query(idx1 - 1);
else
sol[events[j].id] += query(idx2) - query(idx1 - 1);
}
for (int j = 1; j <= m; j++)
{
out << sol[j] << '\n';
}
return 0;
}