Submission #167418

#	Time	Username	Problem	Language	Result	Execution time	Memory
167418		cbertram	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	2797 ms	133388 KiB

joioi

#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<string> vs;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
#define all(x) x.begin(), x.end()
#define rep(i,a,b) for(int i = a; i < b; i++)

int min_above(vi& arr, int key, int l, int r) {
  while(l < r) {
    int m = (l+r)/2;
    if(arr[m] <= key)
      l = m+1;
    else
      r = m;
  }
  return r;
}

int search_best(int H, int W, vi& vmin1, vi& vmax1, vi& vmin2, vi& vmax2) {
  int from = 0;
  int to = 1000000000;
  int bestUntilNow = 1000000000;
  while(from <= to) {
    int mid = (from+to)/2;

    int min1, min2, max1, max2;
    min1 = min2 = 1000000001;
    max1 = max2 = 0;
    rep(h,0,H) {
      int i = min_above(vmax1, mid, h*W, (h+1)*W);
      //if(mid == 24) cerr << h << ": " << i/W << ", " << i%W << '\n';
      if(i > h*W) {
	min1 = min(min1, vmin1[i-1]);
	max1 = max(max1, vmax1[i-1]);
      }
      if(i < (h+1)*W) {
	min2 = min(min2, vmin2[i]);
	max2 = max(max2, vmax2[i]);
      }
    }
    
    int res1 = max1-min1;
    int res2 = max2-min2;
    //if(vmin1[0] == 18) cerr << "mid = " << mid << ", (from, to) = (" << from << ", " << to << "), (res1, res2) = (" << res1 << ", " << res2 <<")\n";
    bestUntilNow = min(bestUntilNow, max(res1, res2));
    if(min1 == 0 || min2 == 0 || res1 < res2)
      from = mid+1;
    else
      to = mid-1;
  }
  return bestUntilNow;
}

int min_above2(vi& arr, int key, int l, int r) {
  while(l < r) {
    int m = (l+r)/2;
    if(arr[m] >= key)
      l = m+1;
    else
      r = m;
  }
  return r;
}

int search_best2(int H, int W, vi& vmin1, vi& vmax1, vi& vmin2, vi& vmax2) {
  int from = 0;
  int to = 1000000000;
  int bestUntilNow = 1000000000;
  while(from < to) {
    int mid = (from+to)/2;

    int min1, min2, max1, max2;
    min1 = min2 = 1000000001;
    max1 = max2 = 0;
    rep(h,0,H) {
      int i = min_above2(vmin1, mid, h*W, (h+1)*W);
      if(i > h*W) {
	min1 = min(min1, vmin1[i-1]);
	max1 = max(max1, vmax1[i-1]);
      }
      if(i < (h+1)*W) {
	min2 = min(min2, vmin2[i]);
	max2 = max(max2, vmax2[i]);
      }
    }
    
    int res1 = max1-min1;
    int res2 = max2-min2;
    bestUntilNow = min(bestUntilNow, max(res1, res2));
    if(max1 == 0 || max2 == 0 || res1 < res2)
      from = mid+1;
    else
      to = mid-1;
  }
  return bestUntilNow;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  int H, W;
  cin >> H;
  cin >> W;
  vi alt1(H*W);
  rep(h,0,H)
    rep(w,0,W) cin >> alt1[w+h*W];

  vi max1(H*W);
  vi min1(H*W);
  vi max2(H*W);
  vi min2(H*W);
  vi alt(H*W);
  int ans = 1000000000;
  rep(j,0,2) {
    rep(i,0,4) {
      if(i == 0) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[w+h*W];
      if(i == 1) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[W-1-w+h*W];
      if(i == 2) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[w+(H-1-h)*W];
      if(i == 3) rep(h,0,H) rep(w,0,W) alt[w+h*W] = alt1[W-1-w+(H-1-h)*W];	
      rep(h,0,H) {
	rep(w,0,W) {
	  max1[w+h*W] = alt[w+h*W];
	  if(w > 0) max1[w+h*W] = max(max1[w+h*W], max1[w-1+h*W]);
	  if(h > 0) max1[w+h*W] = max(max1[w+h*W], max1[w+(h-1)*W]);
	}
      }
      rep(h,0,H) {
	rep(w,0,W) {
	  min1[w+h*W] = alt[w+h*W];
	  if(w > 0) min1[w+h*W] = min(min1[w+h*W], min1[w-1+h*W]);
	  if(h > 0) min1[w+h*W] = min(min1[w+h*W], min1[w+(h-1)*W]);
	}
      }
      rep(h,0,H) {
	rep(w1,0,W) {
	  int w = W-1-w1;
	  max2[w+h*W] = alt[w+h*W];
	  if(w < W-1) max2[w+h*W] = max(max2[w+h*W], max2[w+1+h*W]);
	}
      }
      rep(h,0,H) {
	rep(w1,0,W) {
	  int w = W-1-w1;
	  min2[w+h*W] = alt[w+h*W];
	  if(w < W-1) min2[w+h*W] = min(min2[w+h*W], min2[w+1+h*W]);
	}
      }
      int res;
      if(j == 0) res = search_best(H,W,min1,max1,min2,max2);
      if(j == 1) res = search_best2(H,W,min1,max1,min2,max2);
      //cerr << res << '\n';
      ans = min(ans, res);
    }
  }
  cout << ans << '\n';;
}

• Subtask 1: 15 / 15
• Subtask 2: 45 / 45
• Subtask 3: 40 / 40