Submission #669584

#TimeUsernameProblemLanguageResultExecution timeMemory
669584Dec0DeddThe Kingdom of JOIOI (JOI17_joioi)C++14
60 / 100
4090 ms262144 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace std; using namespace __gnu_pbds; #define sh short const int N = 2e3+110; const int INF = 1e9; int a[N][N], cnt[N], h, w; vector<int> v; struct custom_hash { static uint64_t splitmix64(uint64_t x) { // http://xorshift.di.unimi.it/splitmix64.c x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31); } size_t operator()(uint64_t x) const { static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count(); return splitmix64(x + FIXED_RANDOM); } }; gp_hash_table<int, int, custom_hash> hs; void fs(int &number) { register int c; number = 0; c = getchar(); for (; (c>47 && c<58); c=getchar()) number = number *10 + c - 48; } bool cmp(sh x, sh y) { return a[cnt[x]+1][x] > a[cnt[y]+1][y]; } deque<int> tmp; int solve() { memset(cnt, 0, sizeof(cnt)); hs.clear(); int res=INF, lis=INF, uis=-1; deque<int> q=tmp; priority_queue<sh, vector<sh>, function<bool(sh, sh)>> pq(cmp); pq.push(w); for (int k=0; k<(int)v.size(); ++k) { while (!pq.empty()) { if (a[cnt[pq.top()]+1][pq.top()] <= v[k]) { sh x=pq.top(); pq.pop(); int val=a[cnt[x]+1][x]; ++hs[val]; lis=min(lis, val), uis=max(uis, val); ++cnt[x]; if (cnt[x] == h) continue; if (x == w || cnt[x+1] >= cnt[x]+1) pq.push(x); if (x == 1) continue; if (cnt[x] == cnt[x-1]+1) pq.push(x-1); } else break; } while (!q.empty()) { if (hs[q.front()] > 0) --hs[q.front()], q.pop_front(); else break; } while (!q.empty()) { if (hs[q.back()] > 0) --hs[q.back()], q.pop_back(); else break; } int lf; if (q.empty()) lf=INF; else lf=q.back()-q.front(); res=min(res, max(lf, uis-lis)); } return res; } void hor() { for (int i=1; i<h/2+1; ++i) { for (int j=1; j<=w; ++j) swap(a[i][j], a[h-i+1][j]); } } void ver() { for (int i=1; i<=h; ++i) { for (int j=1; j<w/2+1; ++j) swap(a[i][j], a[i][w-j+1]); } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); fs(h), fs(w); for (int i=1; i<=h; ++i) { for (int j=1; j<=w; ++j) { fs(a[i][j]); v.push_back(a[i][j]); } } sort(v.begin(), v.end()); for (auto u : v) tmp.push_back(u); v.erase(unique(v.begin(), v.end()), v.end()); int ans=solve(); hor(); ans=min(ans, solve()); hor(); ver(); ans=min(ans, solve()); hor(); ans=min(ans, solve()); hor(); printf("%d\n", ans); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...