Cerința

Se citesc două matrice rare și se cere să se calculeze suma lor.

O matrice A(n,m) se numește rară dacă majoritatea elementelor sale sunt egale cu zero (cel puţin jumătate). Datorită numărului mic de numere nenule, o matrice rară A(n,m), având k elemente nenule, poate fi memorată folosind un șir X conţinând k triplete de forma (linie, coloană , valoare), corespunzătoare valorilor nenule ale matricei. Elementele șirului X se memorează în ordine lexicografică după (linie,coloana).

De exemplu matricea cu n = m = 3

1 0 2
0 0 5
0 2 0

se va memora sub forma sirului X continand 4 triplete : {(1,1,1) , (1,3,2) , (2,3,5) , (3,2,2)}.

Date de intrare

Fișierul de intrare matrice_rara.in conține pe prima linie , dimensiunile celor două matrice n m – reprezentând numărul de linii şi coloane, şi N1 N2, numărul de elemente nenule ale matricei A, respectiv matricei B. Apoi următoarele N1 linii vor conține triplete – elementele nenule ale matricei A în ordine lexicografică, iar ultimele N2 linii vor conține triplete reprezentând elementele nenule ale matricei B, tot în ordine lexicografică .

Date de ieșire

Fișierul de ieșire matrice_rara.out va conține pe prima linie numărul de elemente diferite de 0 din matricea sumă C şi apoi matricea în sine sub forma tripletelor în ordine lexicografică, câte unul pe o linie .

Restricții și precizări

• 1 ≤ n , m ≤ 1.000.000
• 1 ≤ N1 , N2 ≤ 300.000
• -1.000.000.000 ≤ A[i][j], B [i][j]≤ 1.000.000.000

Exemplu

matrice_rara.in

5 6 3 3
1 1 2
3 4 3
4 6 1
1 2 3
3 4 -2
4 6 2

matrice_rara.out

4
1 1 2
1 2 3
3 4 1
4 6 3

#include <bits/stdc++.h>
using namespace std;

ifstream cin("matrice_rara.in");
ofstream cout("matrice_rara.out");

struct andra
{
    int i , j , val;
};
andra a[300001] , c[300001] , b[300001];

void citire(andra a[] , int n)
{
    for(int i = 1 ; i <= n ; i++)
        cin >> a[i].i >> a[i].j >> a[i].val;
}

void afisare(andra a[] , int n)
{
    cout << n << '\n';
    for(int i = 1 ; i <= n ; i++)
        cout << a[i].i << " " << a[i].j << " " << a[i].val << '\n';
}

int maimic(andra a , andra b)
{
    return a.i < b.i || a.i == b.i && a.j < b.j;
}

long long  n , m , nc , n1 , n2;

int main()
{
    cin >> n >> m >> n1 >> n2;
    citire(a , n1);
    citire(b , n2);
    int i = 1 , j = 1;
    while(i <= n1 && j <= n2)
    {
        if(maimic(a[i] , b[j])) c[++nc] = a[i++];
        else if(maimic(b[j] , a[i])) c[++nc] = b[j++];
        else
        {
            if(a[i].val + b[j].val != 0)
            {
                c[++nc] = a[i];
                c[nc].val += b[j].val;
            }
            i++;
            j++;
        }
    }
    while(i <= n1) c[++nc] = a[i++];
    while(j <= n2) c[++nc] = b[j++];
    cout << nc << '\n';
    for(int i = 1 ; i <= nc ; i++)
        cout << c[i].i << " " << c[i].j << " " << c[i].val << '\n';
}