La ora de geometrie, Aurel a primit de la profesorul X o temă foarte dificilă: fiind date N segmente orizontale (paralele cu axa Ox), cu extremităţile de coordonate numere naturale, să se numere câte dreptunghiuri speciale pot fi formate în plan, luând în considerare aceste segmente.

Un dreptunghi este special dacă respectă simultan următoarele trei condiţii:
1. Cele patru vârfuri ale dreptunghiului au coordonate numere naturale
2. Laturile dreptunghiului sunt paralele cu axa Ox, respectiv Oy
3. Fiecare dintre cele patru vârfuri ale dreptunghiului aparţine cel puţin unui segment

Cerinţa

Scrieţi un program care să-l ajute pe Aurel să determine numărul de posibilităţi de a plasa un dreptunghi în plan astfel încât să fie dreptunghi special. Deoarece rezultatul poate fi foarte mare, se va determina numărul modulo 946021 (restul împărţirii numărului calculat la 946021).

Date de intrare

Pe prima linie a fişierului de intrare drept.in se află numărul natural N reprezentând numărul de segmente orizontale. Pe următoarele N linii se află câte 3 numere naturale y x1 x2 reprezentând coordonatele segmentelor astfel: y – coordonata verticală (ordonata), x1 şi x2 – coordonatele orizontale (abscisele).

Date de ieşire

Fişierul de ieşire drept.out va conţine un singur număr, reprezentând restul împărţirii numărului total de dreptunghiuri speciale la 946021.

Restricţii şi precizări

1 ≤ N ≤ 50.000
0 ≤ x1≤ x2 ≤ 1.000.000.000
0 ≤ y ≤ 1000
Vârfurile oricărui dreptunghi special sunt distincte două câte două şi nu pot avea toate aceeaşi ordonată
Pentru un număr de teste în valoare de 60 de puncte, N ≤ 5000

Exemple

Exemplul 1

drept.in

drept.out

Exemplul 2

drept.in

drept.out

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema drept:

//autor Adrian Airinei 
//O(YMAX*N)-100 puncte

#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_N 50100
#define MAX_Y 1010

#define MOD 946021

#define PI pair<int, int>

int N, res;
vector< PI > Y[MAX_Y];

void read_data(void)
{
    int i, a, b, y;
    scanf("%d", &N);
    for(i = 1; i <= N; i++)
        scanf("%d %d %d", &y, &a, &b), Y[y].push_back(make_pair(a,b));
}

void normalize(void)
{
    int i, j, k, cnt;
    for(i = 0; i < MAX_Y; i++)
    {
        sort(Y[i].begin(), Y[i].end());
        cnt = 0;
        for(j = 0; j < Y[i].size(); j++)
        {
            k = j;
            while(j+1 < Y[i].size() && Y[i][j+1].first >= Y[i][k].first && Y[i][j+1].first <= Y[i][k].second)
                Y[i][k].second = max(Y[i][k].second, Y[i][j+1].second), j++;
            Y[i][cnt++] = Y[i][k];
        }
        Y[i].resize(cnt);
    }
}

int intersect(PI a, PI b)
{
    if(a.first >= b.first && a.first <= b.second)
        return min(a.second, b.second)-a.first+1;
    if(b.first >= a.first && b.first <= a.second)
        return min(b.second, a.second)-b.first+1;
    return 0;
}

void solve(void)
{
    int i, j, k, indi, indj, r;
    for(i = 0; i < MAX_Y; i++)
        for(j = i+1; j < MAX_Y; j++)
        {
            r = indi = indj = 0;
            while(indi < Y[i].size() && indj < Y[j].size())
            {
                r += intersect(Y[i][indi], Y[j][indj]);
                if(Y[i][indi].second <= Y[j][indj].second)
                    indi++;
                else
                    indj++;
            }
            res += (int) ( (long long)r*(r-1)/2%MOD );
            res %= MOD;
        }
}

int main(void)
{
    freopen("drept.in", "rt", stdin);
    freopen("drept.out", "wt", stdout);
    read_data();
    normalize();
    solve();
    printf("%d
", res);
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #153 drept

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #153 drept de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #153 drept