Cod sursa(job #1166025)

Utilizator stefanzzzStefan Popa stefanzzz Data 3 aprilie 2014 10:03:29
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
#define MAXN 16005
#define MAXM 100005
#define MAXC 100
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");

struct event{
    short int tip;
    int t,nr;};

int n,m,x,cnt,ny,aib[2*MAXM+MAXN],sol[MAXM];
set<int> sy;
set<int>::iterator it;
pair<int,int> pct[MAXN];
pair< pair<int,int>, pair<int,int> > dreptunghi[MAXM];
char s[MAXC];
event aux;
vector<event> ev;
vector<int> vy;
vector<int>::iterator it2;

inline void update_aib(int p);
inline int query_aib(int p);
inline int get_int();
inline bool Comp(event p,event q){
    if(p.t==q.t)
        return p.tip<q.tip;
    return p.t<q.t;};


int main()
{
    int i;
    f>>n;
    f.getline(s,MAXC,'\n');
    aux.tip=1;
    for(i=1;i<=n;i++){
        f.getline(s,MAXC,'\n');
        cnt=0;
        pct[i].first=get_int();
        pct[i].second=get_int();
        sy.insert(pct[i].second);
        aux.t=pct[i].first;
        aux.nr=i;
        ev.push_back(aux);}
    f>>m;
    f.getline(s,MAXC,'\n');
    for(i=1;i<=m;i++){
        f.getline(s,MAXC,'\n');
        cnt=0;
        dreptunghi[i].first.first=get_int();
        dreptunghi[i].first.second=get_int();
        dreptunghi[i].second.first=get_int();
        dreptunghi[i].second.second=get_int();
        sy.insert(dreptunghi[i].first.second);
        sy.insert(dreptunghi[i].second.second);
        aux.nr=i;
        aux.tip=0;
        aux.t=dreptunghi[i].first.first;
        ev.push_back(aux);
        aux.tip=2;
        aux.t=dreptunghi[i].second.first;
        ev.push_back(aux);}
    for(it=sy.begin();it!=sy.end();it++)
        vy.push_back(*it);
    ny=vy.size();
    for(i=1;i<=n;i++)
        pct[i].second=(lower_bound(vy.begin(),vy.end(),pct[i].second)-vy.begin())+1;
    for(i=1;i<=m;i++){
        dreptunghi[i].first.second=(lower_bound(vy.begin(),vy.end(),dreptunghi[i].first.second)-vy.begin())+1;
        dreptunghi[i].second.second=(lower_bound(vy.begin(),vy.end(),dreptunghi[i].second.second)-vy.begin())+1;}
    sort(ev.begin(),ev.end(),Comp);
    for(i=0;i<ev.size();i++){
        aux=ev[i];
        if(aux.tip==1){
            update_aib(pct[aux.nr].second);
            continue;}
        x=query_aib(dreptunghi[aux.nr].second.second)-query_aib(dreptunghi[aux.nr].first.second-1);
        if(aux.tip)
            sol[aux.nr]+=x;
        else
            sol[aux.nr]-=x;}
    for(i=1;i<=m;i++)
        g<<sol[i]<<'\n';
    f.close();
    g.close();
    return 0;
}

inline int get_int(){
    int semn;
    if(s[cnt]=='-'){
        semn=-1;
        ++cnt;}
    else
        semn=1;
    x=s[cnt++]-'0';
    while(s[cnt]>='0'&&s[cnt]<='9')
        x=x*10+s[cnt++]-'0';
    cnt++;
    return semn*x;}

inline void update_aib(int p){
    while(p<=ny){
        aib[p]++;
        p+=(p&(-p));}}

inline int query_aib(int p){
    int S=0;
    while(p){
        S+=aib[p];
        p-=(p&(-p));}
    return S;}