Submission #815767

#	Time	Username	Problem	Language	Result	Execution time	Memory
815767		beaconmc	Garden (JOI23_garden)	C++14	15 / 100	3086 ms	56188 KiB

garden

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)



vector<ll> merge(vector<ll> &a, vector<ll> &b){
  ll l=0;
  ll r = 0;
  vector<ll> ans;
  while (!(l==a.size() && r==b.size())){
    if (l==a.size()){
      ans.push_back(b[r]);
      r++;
    }else if (r==b.size()){
      ans.push_back(a[l]);
      l++;
    }else{
      if (a[l] <= b[r]){
        ans.push_back(a[l]);
        l++;
      }else{
        ans.push_back(b[r]);
        r++;
      }
    }
  }
  return ans;
}


int main(){
    fast();
    ll n,m,d;
    cin >> n >> m >> d;
    vector<vector<ll>> a,b;

    FOR(i,0,n){
      vector<ll> temp(2);
      cin >> temp[0] >> temp[1];
      a.push_back(temp);
    }

    FOR(i,0,m){
      vector<ll> temp(2);
      cin >> temp[0] >> temp[1];
      b.push_back(temp);
    }

    vector<ll> X;
    vector<ll> Y;

    for (auto&i : a){
      X.push_back(i[0]);
      Y.push_back(i[1]);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());

    ll ans = 1000000000000;

    FOR(i,0,1<<(b.size())){
      vector<ll> x,y, tempx, tempy;
      x = X;
      y = Y;

      FOR(j,0,b.size()){
        if (i&(1<<j)){
          tempx.push_back(b[j][0]);
        }else{
          tempy.push_back(b[j][1]);
        }
      }
      sort(tempx.begin(), tempx.end());
      sort(tempy.begin(), tempy.end());
      x = merge(x, tempx);
      y = merge(y, tempy);

      ll xx = 1000000000000;
      ll yy = 1000000000000;

      FOR(i,0,x.size()-1){
        xx = min(xx, d-(x[i+1]-x[i])+1);

      }
      xx = min(xx, x[x.size()-1]-x[0]+1);

      FOR(i,0,y.size()-1){
        yy = min(yy, d-(y[i+1]-y[i])+1);
      }
      yy = min(yy, y[y.size()-1]-y[0]+1);
      ans = min(ans, xx*yy);
    }
    cout << ans;

}

Compilation message (stderr)

garden.cpp: In function 'std::vector<long long int> merge(std::vector<long long int>&, std::vector<long long int>&)':
garden.cpp:20:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while (!(l==a.size() && r==b.size())){
      |            ~^~~~~~~~~~
garden.cpp:20:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |   while (!(l==a.size() && r==b.size())){
      |                           ~^~~~~~~~~~
garden.cpp:21:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |     if (l==a.size()){
      |         ~^~~~~~~~~~
garden.cpp:24:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     }else if (r==b.size()){
      |               ~^~~~~~~~~~
garden.cpp: In function 'int main()':
garden.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   76 |       FOR(j,0,b.size()){
      |           ~~~~~~~~~~~~             
garden.cpp:76:7: note: in expansion of macro 'FOR'
   76 |       FOR(j,0,b.size()){
      |       ^~~
garden.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   91 |       FOR(i,0,x.size()-1){
      |           ~~~~~~~~~~~~~~           
garden.cpp:91:7: note: in expansion of macro 'FOR'
   91 |       FOR(i,0,x.size()-1){
      |       ^~~
garden.cpp:9:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define FOR(i, x, y) for(ll i=x; i<y; i++)
......
   97 |       FOR(i,0,y.size()-1){
      |           ~~~~~~~~~~~~~~           
garden.cpp:97:7: note: in expansion of macro 'FOR'
   97 |       FOR(i,0,y.size()-1){
      |       ^~~

• Subtask 1: 15 / 15
• Subtask 2: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25