Pagini recente » Cod sursa (job #2752992) | Cod sursa (job #2752969)
#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];
class Parser
{
private:
static const int BUFF_SIZE = 5000000;
ifstream in;
char buffer[BUFF_SIZE];
int posBuff;
public:
Parser(char* file)
{
in = ifstream(file);
posBuff = BUFF_SIZE - 1;
}
int getInt()
{
int rez = 0;
while (!('0' <= buffer[posBuff] && buffer[posBuff] <= '9'))
{
posBuff++;
if (posBuff == BUFF_SIZE)
{
posBuff = 0;
in.read(buffer, BUFF_SIZE);
}
}
while ('0' <= buffer[posBuff] && buffer[posBuff] <= '9')
{
rez = rez * 10 + buffer[posBuff] - '0';
posBuff++;
if (posBuff == BUFF_SIZE)
{
posBuff = 0;
in.read(buffer, BUFF_SIZE);
}
}
return rez;
}
};
Parser input("zoo.in");
int main()
{
ofstream out("zoo.out");
n = input.getInt();
v.reserve(n);
for (int i = 1; i <= n; i++)
{
int x, y;
x = input.getInt();
y = input.getInt();
v.emplace_back(x, y);
}
sort(v.begin(), v.end());
coordX.reserve(1 + n);
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;
m = input.getInt();
events.reserve(2 * m);
for (int j = 1; j <= m; j++)
{
int x1, y1, x2, y2;
x1 = input.getInt();
y1 = input.getInt();
x2 = input.getInt();
y2 = input.getInt();
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;
}