Submission #958230

#TimeUsernameProblemLanguageResultExecution timeMemory
958230Vladth11Hamburg Steak (JOI20_hamburg)C++14
3 / 100
3051 ms19592 KiB
#include <bits/stdc++.h> #define debug(x) cerr << #x << " " << x << "\n" #define debugs(x) cerr << #x << " " << x << " " #pragma GCC optimize ("Ofast") #pragma GCC target ("avx2") #define int ll using namespace std; typedef long long ll; typedef pair <ll, ll> pii; const ll NMAX = 1000001; const ll INF = 1e9; const ll nrbits = 20; const ll MOD = 998244353; struct rect { int x1, y1, x2, y2; } q[NMAX]; rect buckets[4]; int last[NMAX]; rect combine(rect a, rect b){ rect sol = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)}; return sol; } signed main() { #ifdef HOME ifstream cin(".in"); ofstream cout(".out"); #endif // HOME ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, i, k; cin >> n >> k; queue <int> qq; for(i = 1; i <= n; i++) { cin >> q[i].x1 >> q[i].y1 >> q[i].x2 >> q[i].y2; qq.push(i); } for(int j = 1; j <= k; j++) { buckets[j] = {0, 0, INF, INF}; } int cnt = 0; while(qq.size()) { int acum = qq.front(); qq.pop(); if(cnt == last[acum]) { for(int j = 1; j <= k; j++) { rect inters = combine(q[acum], buckets[j]); if(inters.x1 <= inters.x2 && inters.y1 <= inters.y2){ buckets[j] = inters; break; } } cnt++; /// sigur am intrat intr-un bucket }else{ int oke = 0; int care = 0; for(int j = 1; j <= k; j++) { rect inters = combine(q[acum], buckets[j]); if(inters.x1 <= inters.x2 && inters.y1 <= inters.y2){ care = j; oke++; } } if(oke == 1){ buckets[care] = combine(q[acum], buckets[care]); cnt++; }else{ qq.push(acum); /// oke sigur e mai mare ca 0 } } last[acum] = cnt; } for(i = 1; i <= k; i++){ cout << buckets[i].x1 << " " << buckets[i].y1 << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...