Submission #217750

#TimeUsernameProblemLanguageResultExecution timeMemory
217750TheLoraxHamburg Steak (JOI20_hamburg)C++11
15 / 100
1404 ms70264 KiB
#include <bits/stdc++.h> //#pragma GCC optimize ("O3") //#pragma GCC optimize ("Ofast") #define F first #define S second #define MT make_tuple #define MP make_pair #define SZ(a) ((int)(a).size()) #define PB push_back #define LBS 20 #define MOD ((long long)1e9+7) //1e9+9 #define LEFT(i) (2*(i)) #define RIGHT(i) (2*(i)+1) #define PAR(i) ((i)/2) #define ALL(a) (a).begin(), (a).end() #define END(s) {cout << s;return;} using namespace std; typedef long long ll; typedef double rat; typedef long long bi; typedef pair<ll, ll> ii; typedef std::vector<ii> vii; typedef std::map<ll, ll> mii; typedef bitset<LBS> bis; typedef std::vector<bis> vbs; typedef priority_queue<ii, std::vector<ii>, greater<ii> > minpq; typedef priority_queue<ii, std::vector<ii>, less<ii> > maxpq; typedef priority_queue<ii> pq; struct ham{ ll l, d, r, u; }; template<class T> void in(T &a){ for(auto &x: a) cin >> x; } template<class T> void out(T &a, string sep=" "){ for(auto x: a) cout << x<<sep; cout << '\n'; } template<class T> void err(T &a, string sep=" "){ for(auto x: a) cerr << x <<sep; cerr << '\n'; } std::vector<ham> h; std::vector<int> ma; std::vector<ii> ou; int n, k; void end(){ for(auto &x: ou) cout << x.F<<" "<<x.S<<"\n"; exit(0); } template<class T> void pop(T &pq){ while (!pq.empty() && ma[pq.top().S]) pq.pop(); if(pq.empty()) end(); } void rek(minpq pqxi, maxpq pqxa, minpq pqyi, maxpq pqya, int idx=0){ pop(pqxi); pop(pqxa); pop(pqyi); pop(pqya); if(idx==k) return; ll xmi=pqxi.top().F; ll xma=pqxa.top().F; ll ymi=pqyi.top().F; ll yma=pqya.top().F; for(auto &c: {MP(xmi,ymi),MP(xmi,yma),MP(xma,ymi),MP(xma,yma)}){ ou[idx]=c; for(int i=0; i<n; i++) if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u) ma[i]++; rek(pqxi, pqxa, pqyi, pqya, idx+1); for(int i=0; i<n; i++) if(h[i].l<=c.F && c.F<=h[i].r && h[i].d<=c.S && c.S<=h[i].u) ma[i]--; } if(idx==0 && k==4){ ii vxa={0,1000000000}, vxi={0,1000000000}, vya={0,1000000000}, vyi={0,1000000000}; for(int i=0; i<n; i++){ if(h[i].l<=xma){ vxa.F=max(vxa.F,h[i].d); vxa.S=min(vxa.S,h[i].u); } else if(h[i].r>=xmi){ vxi.F=max(vxi.F,h[i].d); vxi.S=min(vxi.S,h[i].u); } else if(h[i].d<=yma){ vya.F=max(vya.F,h[i].l); vya.S=min(vya.S,h[i].r); } else if(h[i].l<=ymi){ vyi.F=max(vyi.F,h[i].l); vyi.S=min(vyi.S,h[i].r); } } if(vxa.F>vxa.S || vxi.F>vxi.S || vya.F>vya.S || vyi.F>vyi.S){ for(unsigned int i=1; i<0; i++) i++; } ou[0]=MP(xma,vxa.F); ou[1]=MP(xmi,vxi.F); ou[2]=MP(yma,vya.F); ou[3]=MP(ymi,vyi.F); end(); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> k; minpq pqxi, pqyi; maxpq pqxa, pqya; h.resize(n); ou.resize(k); ma.resize(n,0); for(int i=0; i<n; i++){ cin >> h[i].l>>h[i].d>>h[i].r>>h[i].u; pqxi.emplace(h[i].r,i); pqxa.emplace(h[i].l,i); pqyi.emplace(h[i].u,i); pqya.emplace(h[i].d,i); } rek(pqxi, pqxa, pqyi, pqya); }
#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...