Road Signs
Летен Турнир по Информатика, 2018
Time Limit: 0.5s, Memory Limit: 128MiB
Ели живее на безкрайно дълга права улица, движеща се от запад на изток. По нея има разположени N пътни знака с числа от двете си страни. i-тият знак се намира на Pi метра на изток от къщата на Ели (като Pi може да бъде и отрицателно, в случай, че знакът се намира на запад от къщата на момичето). Всеки знак има изписани числата Wi на страната, виждана от пътуващите от изток на запад, и Ei на страната, виждана от пътуващите от запад на изток.

Ели не знае за какво са тези знаци. Момичето подозира, че числата обозначават разстоянието (в метри) от всеки от знаците до някакви две много важни точки. Разбира се, различните знаци могат да сочат към различни точки.

Сега Ели се чуди кои са най-важните двойки точки на пътя. Момичето определя "важността" на двойка точки X и Y като броя знаци, които сочат поне една от двете. По-формално, важността за двойка точки с координати X и Y се определя като броя на всички знаци, за които поне едно от следните е изпълнено:

Pi - Wi = X Pi - Wi = Y Pi + Ei = X Pi + Ei = Y

Точките X и Y могат да са с произволни координати, включително отрицателни такива - както казахме, улицата е безкрайно дълга и в двете посоки.

Възможно е да има повече от една двойка "най-важни" точки: например, ако K знака сочат точките X1 и Y1, но също така K (потенциално различни) знака сочат X2 и Y2. Сега Ели иска да намери колко важни са най-важните точки, и колко двойки такива точки има.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броят знаци. На всеки от следващите N реда ще бъдат зададени по три цели числа Pi, Wi, и Ei – съответно позицията на знака; числото, виждано от пътуващите от изток на запад; и числото, виждано от пътуващите от запад на изток. Знаците ще са зададени в нарастващ ред на позицията си Pi, като няма да има два знака с една и съща позиция. Също така няма да има точка, която е сочена от всички знаци.
Изход
На единствен ред на стандартния изход изведете две цели числа – колко е важността на най-важните двойки точки, и броя различни двойки такива точки.
Ограничения
  • 2 ≤ N ≤ 100,000
  • 1 ≤ Ei, Wi ≤ 1,000,000
  • -1,000,000 ≤ PiPj ≤ 1,000,000
Примерен Вход Примерен Изход
11 -17 10 19 -8 2 50 -2 11 3 0 13 42 3 2 6 7 33 15 11 10 31 12 25 4 13 10 7 14 10 10 17 16 25 6 3
24 -10 9 1 -9 20 10 -8 1 11 -7 12 17 -6 20 16 -5 22 13 -4 30 6 -3 20 7 -2 25 16 -1 3 21 0 30 7 1 17 22 2 9 5 3 25 18 4 21 13 5 16 17 6 4 5 7 15 8 8 11 24 9 26 3 10 25 14 11 2 21 12 22 5 13 24 17 4 42
В първия пример важността на най-важните двойки точки е 6. Съществуват три двойки такива точки:
X1 = -13, Y1 = 1 (със сочещи ги знаци {3, 4, 5, 7, 8, 11}),
X2 = -13, Y2 = 42 (със сочещи ги знаци {2, 3, 4, 7, 8, 11}),
X3 = 1, Y3 = 42 (със сочещи ги знаци {2, 3, 4, 5, 7, 11}).

Във втория пример всички най-важни двойки точки са:
(-27, -19), (-27, -17), (-27, -11), (-27, -9), (-27, 2), (-27, 7), (-27, 10), (-27, 17), (-27, 32), (-19, -17), (-19, -11), (-19, 2), (-19, 7), (-19, 17), (-19, 32), (-17, -11), (-17, -9), (-17, 2), (-17, 7), (-17, 10), (-17, 32), (-11, -9), (-11, 2), (-11, 7), (-11, 10), (-11, 17), (-11, 32), (-9, 2), (-9, 7), (-9, 10), (-9, 17), (-9, 32), (2, 7), (2, 10), (2, 17), (2, 32), (7, 10), (7, 17), (7, 32), (10, 17), (10, 32), (17, 32)}
Мрън!