Submission #217750

#	Time	Username	Problem	Language	Result	Execution time	Memory
217750		TheLorax	Hamburg Steak (JOI20_hamburg)	C++11	15 / 100	1404 ms	70264 KiB

hamburg

#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);
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79