Submission #217737

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
217737	2020-03-30T14:51:53 Z	TheLorax	Hamburg Steak (JOI20_hamburg)	C++11	15 / 100	1283 ms	70296 KB

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]--;
  }
}

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.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	768 KB	Output is correct
2	Correct	3 ms	768 KB	Output is correct
3	Correct	2 ms	768 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct

Subtask #2
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	896 KB	Output is correct
2	Correct	3 ms	900 KB	Output is correct
3	Correct	2 ms	896 KB	Output is correct
4	Correct	3 ms	912 KB	Output is correct

Subtask #3
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1024 KB	Output is correct
2	Correct	2 ms	1024 KB	Output is correct
3	Correct	2 ms	1024 KB	Output is correct
4	Correct	2 ms	1024 KB	Output is correct
5	Correct	2 ms	1024 KB	Output is correct
6	Correct	2 ms	1024 KB	Output is correct
7	Correct	2 ms	1024 KB	Output is correct
8	Correct	3 ms	1048 KB	Output is correct
9	Correct	8 ms	1112 KB	Output is correct
10	Correct	5 ms	1100 KB	Output is correct
11	Correct	4 ms	1036 KB	Output is correct
12	Correct	4 ms	1080 KB	Output is correct

Subtask #4
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1152 KB	Output is correct
2	Correct	2 ms	1152 KB	Output is correct
3	Correct	2 ms	1152 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	2 ms	1152 KB	Output is correct
6	Correct	3 ms	1152 KB	Output is correct
7	Correct	3 ms	1152 KB	Output is correct
8	Correct	3 ms	1152 KB	Output is correct
9	Correct	9 ms	1156 KB	Output is correct
10	Correct	5 ms	1200 KB	Output is correct
11	Correct	4 ms	1184 KB	Output is correct
12	Correct	3 ms	1164 KB	Output is correct
13	Correct	23 ms	1184 KB	Output is correct
14	Incorrect	20 ms	1232 KB	Unexpected end of file - int32 expected
15	Halted	0 ms	0 KB	-

Subtask #5
1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	768 KB	Output is correct
2	Correct	3 ms	768 KB	Output is correct
3	Correct	2 ms	768 KB	Output is correct
4	Correct	2 ms	768 KB	Output is correct
5	Correct	181 ms	45084 KB	Output is correct
6	Correct	191 ms	45084 KB	Output is correct
7	Correct	193 ms	45088 KB	Output is correct
8	Correct	188 ms	45068 KB	Output is correct

Subtask #6
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	896 KB	Output is correct
2	Correct	3 ms	900 KB	Output is correct
3	Correct	2 ms	896 KB	Output is correct
4	Correct	3 ms	912 KB	Output is correct
5	Correct	216 ms	54872 KB	Output is correct
6	Correct	317 ms	57552 KB	Output is correct
7	Correct	236 ms	56088 KB	Output is correct
8	Correct	346 ms	57732 KB	Output is correct

Subtask #7
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1024 KB	Output is correct
2	Correct	2 ms	1024 KB	Output is correct
3	Correct	2 ms	1024 KB	Output is correct
4	Correct	2 ms	1024 KB	Output is correct
5	Correct	2 ms	1024 KB	Output is correct
6	Correct	2 ms	1024 KB	Output is correct
7	Correct	2 ms	1024 KB	Output is correct
8	Correct	3 ms	1048 KB	Output is correct
9	Correct	8 ms	1112 KB	Output is correct
10	Correct	5 ms	1100 KB	Output is correct
11	Correct	4 ms	1036 KB	Output is correct
12	Correct	4 ms	1080 KB	Output is correct
13	Correct	211 ms	67564 KB	Output is correct
14	Correct	228 ms	67740 KB	Output is correct
15	Correct	209 ms	67444 KB	Output is correct
16	Correct	215 ms	68764 KB	Output is correct
17	Correct	205 ms	67988 KB	Output is correct
18	Correct	218 ms	69016 KB	Output is correct
19	Correct	254 ms	66080 KB	Output is correct
20	Correct	335 ms	69404 KB	Output is correct
21	Correct	1283 ms	70192 KB	Output is correct
22	Correct	764 ms	70168 KB	Output is correct
23	Correct	525 ms	70172 KB	Output is correct
24	Correct	801 ms	70296 KB	Output is correct

Subtask #8
0 / 79.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1152 KB	Output is correct
2	Correct	2 ms	1152 KB	Output is correct
3	Correct	2 ms	1152 KB	Output is correct
4	Correct	3 ms	1152 KB	Output is correct
5	Correct	2 ms	1152 KB	Output is correct
6	Correct	3 ms	1152 KB	Output is correct
7	Correct	3 ms	1152 KB	Output is correct
8	Correct	3 ms	1152 KB	Output is correct
9	Correct	9 ms	1156 KB	Output is correct
10	Correct	5 ms	1200 KB	Output is correct
11	Correct	4 ms	1184 KB	Output is correct
12	Correct	3 ms	1164 KB	Output is correct
13	Correct	23 ms	1184 KB	Output is correct
14	Incorrect	20 ms	1232 KB	Unexpected end of file - int32 expected
15	Halted	0 ms	0 KB	-

Submission #217737

Compilation message