Cod sursa(job #3255375)

Utilizator unomMirel Costel unom Data 10 noiembrie 2024 15:10:55
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <fstream>
#include <map>
#include <unordered_map>
#include <algorithm>

using namespace std;

struct el
{
    int sw; //0 daca e animal, 1 daca e margine de query
    int x, y1, y2;
    int id, sf;
};

ifstream in("zoo.in");
ofstream out("zoo.out");
int n, m, p, cnt;
pair<int, int> v[16005];
pair<pair<int, int>, pair<int, int>> w[100005];
map<int, int> mp;
unordered_map<int, int> norm;
el vec[216005];
int aib[216005];
int ans[100005];

bool cmp(const el &a, const el &b)
{
    if(a.x == b.x)
    {
        return a.sw < b.sw;
    }
    else
    {
        return a.x < b.x;
    }
}

void update(int x, int poz)
{
    for(int i = poz; i<=cnt; i+=(i&-i))
    {
        aib[i] += x;
    }
}

int query(int poz)
{
    int sum = 0;

    for(int i = poz ; i>=1; i-=(i&-i))
    {
        sum += aib[i];
    }

    return sum;
}

int main()
{
    in>>n;
    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;

        mp[v[i].second] = 1;
    }

    in>>m;
    for(int i = 1; i<=m; i++)
    {
        in>>w[i].first.first>>w[i].first.second>>w[i].second.first>>w[i].second.second;

        mp[w[i].first.second] = 1;
        mp[w[i].second.second] = 1;
    }

    cnt = 0;
    for(auto it: mp)
    {
        cnt++;

        norm[it.first] = cnt;
    }

    for(int i = 1; i<=n; i++)
    {
        v[i].second = norm[v[i].second];

        //out<<v[i].first<<" "<<v[i].second<<'\n';

        p++;
        vec[p] = {0, v[i].first, v[i].second, 0, 0, 0};
    }
    for(int i = 1; i<=m; i++)
    {
        w[i].first.second = norm[w[i].first.second];
        w[i].second.second = norm[w[i].second.second];

        //out<<w[i].first.first<<" "<<w[i].first.second<<" "<<w[i].second.first<<" "<<w[i].second.second<<'\n';

        p++;
        vec[p] = {1, w[i].first.first - 1, w[i].first.second, w[i].second.second, i, 0};

        p++;
        vec[p] = {1, w[i].second.first, w[i].first.second, w[i].second.second, i, 1};
    }

    sort(vec + 1, vec + p + 1, cmp);

    for(int i = 1; i<=p; i++)
    {
        if(vec[i].sw == 0)
        {
            update(1, vec[i].y1);
        }
        else
        {
            int s = query(vec[i].y2) - query(vec[i].y1 - 1);

            if(vec[i].sf == 0)
            {
                ans[vec[i].id] -= s;
            }
            else
            {
                ans[vec[i].id] += s;
            }
        }
    }

    for(int i = 1; i<=m; i++)
    {
        out<<ans[i]<<'\n';
    }

    return 0;
}