10-11 класс

Есеп B. Machine Vision

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

2 seconds

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

256 megabytes

\includegraphics[width=0.25\textwidth,natwidth=360,natheight=300,height=100pt]{abbey_road.png} Өзінің жаңа стартапы үшін НурлашКО, суреттен мәтін шығаруды талап етті. Прототип кезеңінде болғандықтан, Muugle Cloud Vision API платформасындағы дайын шешімді қолдануды жөн көрді. Алайда, түсінікті мәтінді алумен бір мәселе туып отыр. Жіберілген суретке мәтіннің орнына бөлек сөздер мен оладрың орналасқан төртбұрышты аумақ ретінде жауап келеді. НурлашКОға сіздің көмегіңіз қажет — сөздерді кере орналастырып, мәнді мәтін алуға көмектесіңіз. Ресми түрде, сізге $N$ жақтары координаттар өстеріне қатар төртбұрыштар мен әр қайсысына сәйкес сөз берілген. $B$ төртбұрышы мен $A$ төртбұрышының проекцияларының ординаттар өсіне қараған қиылысының ауданы оң болғанда және $B$ $A$-ға ең жақын болып табылғанда тек сол және сол ғана жағдайда $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$ төртбұрышы жақынырақ орналасқан. $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
*/