Областная олимпиада по информатике 2019 год

Задача B. Machine Vision

Ограничение по времени:

2 секунды

Ограничение по памяти:

256 мегабайт

\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} НурлашКО для своего нового стартапа потребовалось получать текст по фотографии. Так как он только на стадии прототипа, его друг предложил использовать готовое решение предоставляемое платформой Muugle Cloud Vision API. Однако, возникла небольшая проблема в работе с этой платформой. В ответ на отправленную фотографию возвращался не текст, а отдельные слова и их локации в виде прямоугольников. Помогите НурлашКО переупорядочить слова и получить осмысленный текст. Более формально. Вам будет дано $N$ прямоугольников со сторонами параллельными осям координат и слова соответствующие каждому из них. Прямоугольник $B$ является соседом $A$ тогда и только тогда когда площадь пересечения их проекций на ось ординат положительна и $B$ ближайший, слева или справа от $A$, среди всех таких. Строчкой называется максимальное по включению подмножество прямоугольников где от каждого прямоугольника можно добраться до любого другого, возможно переходя по соседям. Высота строчки определяется высотой самого высокого прямоугольника в ней. Выведите все строчки предварительно упорядочив их по высоте в порядке убывания. В самой строчке для каждого прямоугольника выведите соответствующую ему слово в порядке от самого левого к правому. Гарантируется что если $A$ является соседом $B$, то и $B$ является соседом $A$. Соседи для прямоугольника, если таковые есть, всегда определяются однозначно. Смотрите замечание к тестовому примеру для лучшего понимания.

Формат входного файла

Первая строка входного файла содержит единственное целое положительное число $N(1 <=q N <=q 2*10^5)$ — количество прямоугольников. Каждая из следующих $N$ строке содержит строчку из маленьких латинских букв и цифр $s_i (1 <=q |s_i| <=q 100000)$ и четыре целых числа $xl_i$, $yb_i$, $xr_i$, $yt_i$ $(1 <=q xl_i, yb_i, xr_i, yt_i <=q 10^9)$ — слово соответствующее прямоугольнику, координаты левого нижнего и правого верхнего угла соответственно. Гарантируется что сумма длин всех $s_i$ не превосходит $2*10^5$. Также гарантируется что никакие два прямоугольника не пересекаются и не вкладываются, но могут касаться.

Формат выходного файла

Выведите ответ на задачу в соответствии с форматом описанным в условии. Каждую строчку следует выводить в отдельной строке. Слова следует разделять единичным пробелом.

Система оценки

Данная задача содержит две подзадачи:

1. $1 <=q N <=q 2000$. Оценивается в $30$ баллов.
2. $1 <=q N <=q 200000$. Оценивается в $70$ баллов.

Пример:

Вход

7
1 9 1 10 3
New 5 3 11 5
Happy 1 2 4 4
2 4 0 5 2
9 10 0 11 2
Year 11 2 15 4
0 6 1 7 3

Ответ

Happy New Year
2 0 1 9

Замечание

\includegraphics[width=0.5\textwidth,natwidth=610,natheight=450]{example2.png} Обратите внимание, что прямоугольники с цифрами $2$ и $0$ не могут быть соседями для прямоугольника со словом $Happy$. В первом случае площадь проекций $Happy$ и $2$ на ординату равна нулю. Во втором случае хоть и площадь пересечения равна единице, но прямоугольник $New$ находится ближе, в тоже время имея положительную площадь пересечения и именно он будет соседом $Happy$. Расстояние между двумя прямоугольниками $A$ и $B$ - это кратчайшее среди всех попарных расстояний от множества точек ограниченных прямоугольником $A$ до множества точек ограниченного прямоугольником $B$. ( Nurlan Zhusupov )

Комментарий/решение

ACCEPTED

показать/скрыть код

#include <bits/stdc++.h>
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define all(v) v.begin(),v.end()
#define pb push_back
#define sz size()
#define ft first
#define sd second
 
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef unsigned long long ull;
 
const int N = 1e6 + 5;
const ll M = 1e8;
const ll inf = 1e18;
const ll mod = 1e9;
const double Pi = acos(-1); 
 
ll binpow(ll x, ll ti) { ll res = 1;while (ti){if(ti & 1)res *= x;x *= x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll binmul(ll x, ll ti) { ll res = 0;while (ti){if(ti & 1)res += x;x += x;ti >>= 1; x %= mod; res %= mod;} return res;}
ll nok(ll a, ll b) { return (a*b)/__gcd(abs(a),abs(b)) * (a*b > 0 ? 1 : -1); }
bool odd(ll n) { return (n % 2 == 1); }
bool even(ll n) { return (n % 2 == 0); }            
 
struct query {
	string s;
	ll x1, y1, x2, y2;
};

ll n;
query a[N];
 
const void solve(/*Armashka*/) {
	cin >> n;
	multiset <pll> st;
	for (int i = 1; i <= n; ++ i) {
		cin >> a[i].s >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
		st.insert({a[i].y2, i});
	}
	multiset <pair<ll, string>> res;
	ll cur = st.rbegin()->sd;
	cur = a[cur].y1;
	for (auto it = --st.end();; -- it) {

		if (a[it->sd].y2 > cur) {
			res.insert({a[it->sd].x1, a[it->sd].s});
		} else {
			for (auto [x, s] : res) cout << s << " ";
			cout << "\n";
			res.clear();
			cur = a[it->sd].y1;
			res.insert({a[it->sd].x1, a[it->sd].s});
		}

		if (it == st.begin()) break; 
	}
	for (auto [x, s] : res) cout << s << " ";
	cout << "\n";
			
}
            
signed main() {
    fast;
    //freopen("divide.in", "r", stdin);
    //freopen("divide.out", "w", stdout);
    int tt = 1;
	//cin >> tt;
    while (tt --) {                                                             
        solve();
    }
}
 
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/