Pagini recente » Cod sursa (job #3134054) | Cod sursa (job #2752299)
#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(), comp);
coordX.emplace_back(v[0].first);
for (int i = 1; i < v.size(); i++)
{
if (v[i].first != v[i - 1].first)
{
coordX.emplace_back(v[i].first);
}
}
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)
{
int pos = lower_bound(coordX.begin(), coordX.end(), v[idx].first) - coordX.begin();
update(1 + pos, 1);
idx++;
}
if (events[j].tip == 1)
{
int idx1 = lower_bound(coordX.begin(), coordX.end(), events[j].st) - coordX.begin() - 1;
int idx2 = upper_bound(coordX.begin(), coordX.end(), events[j].dr) - coordX.begin() - 1;
if (idx2 == -1) continue;
sol[events[j].id] -= query(idx2 + 1) - query(max(idx1 + 1, 0));
}
else
{
int idx1 = lower_bound(coordX.begin(), coordX.end(), events[j].st) - coordX.begin() - 1;
int idx2 = upper_bound(coordX.begin(), coordX.end(), events[j].dr) - coordX.begin() - 1;
if (idx2 == -1) continue;
sol[events[j].id] += query(idx2 + 1) - query(max(idx1 + 1, 0));
}
}
for (int j = 1; j <= m; j++)
{
out << sol[j] << '\n';
}
return 0;
}