Cod sursa(job #3166257)

Utilizator StefannnnnStefan Stefannnnn Data 8 noiembrie 2023 00:40:42
Problema Xor Max Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.09 kb
#include <bits/stdc++.h>

using namespace std;

const int add = 1e6 + 1;

int aib[add * 2];

void update(int x, int adg) { // aib update
    while(x < add * 2) {
        aib[x] += adg;
        x += (x & (-x));
    }
}

int query(int x) { // aib query
    int sum = 0;
    while(x > 0) {
        sum += aib[x];
        x -= (x & (-x));
    }
    return sum;
}

int main() {
    int n; // nr de linii
    cin >> n; // citim
    vector<vector<pair<int, int>>> lin(2 * add + 1); // salvam doar pe linie si pe coloana ca nu avem memorie de n ^ 2
    vector<vector<int>> paib(2 * add + 1), eraib(2 * add + 1); // paib este petru add pe aib, eraib este pentru erase in aib
    for(int i = 1; i <=n; i ++) { // parcurgem coordonatele
        int x, y, a, b; // coordonatele
        cin >> x >> y >> a >> b; // citim
        x += add; // ca sa nu avem probleme cu indici negativi
        y += add; // ca sa nu avem probleme cu indici negativi
        a += add; // ca sa nu avem probleme cu indici negativi
        b += add; // ca sa nu avem probleme cu indici negativi
        if(x == a) { // este paralela cu solul
            if(y < b) {
                swap(y, b); // sa ne fie mai usor ulterior
            }
            paib[b].push_back(x); // cand adaugam in aib
            eraib[y].push_back(x);  // cand scadem din aib
        } else { // e perpendiculara cu solul
            lin[y].push_back({min(a, x), max(a, x)}); // salvam linia
        }
    }
    long long ans = 0; // raspunsul poate fi mare si nu avem mod, deci ne trebuie long long
    for(int j = 1; j < add * 2; j ++) { // parcurgem toate dreptele paralele cu solul, asta fiind sweepline-ul
        for(auto it : paib[j]) {
            update(it, 1); // bagam in aib
        }
        for(auto it : lin[j]) {
            ans += query(it.second) - query(it.first - 1); // calculam pentru fiecare perpendiculara cate puncte de intersectie are in intervalul ei
        }
        for(auto it : eraib[j]) {
            update(it, -1); // scadem din aib
        }
    }
    cout << ans; // afisare raspuns
    return 0;
}