#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 2e9;
ll n, m; int k;
ll X[302], Y[302];
int rx[302], ry[302], sx, sy;
ll ans = LLONG_MAX;
struct Event{
ll x, y, v;
Event(){}
Event(ll x, ll y, ll v): x(x), y(y), v(v){}
bool operator<(const Event &r)const{
if(x!=r.x) return x<r.x;
return v > r.v;
}
} vec[1002];
struct Interval{
ll l, r; /// ���� ����
ll ldist, rdist, mdist; /// �ּ� ����
Interval(){}
Interval(ll l, ll r, ll ldist, ll rdist, ll mdist): l(l), r(r), ldist(ldist), rdist(rdist), mdist(mdist){}
bool operator<(const Interval &nxt)const{
return l<nxt.l;
}
};
vector<ll> vx, vy;
struct diffTree{
int cnt[1024];
ll lv[1024], rv[1024], diff[1024];
inline void merge(int i){
cnt[i] = cnt[i*2] + cnt[i*2+1];
lv[i] = min(lv[i*2], lv[i*2+1]);
rv[i] = max(rv[i*2], rv[i*2+1]);
diff[i] = max({diff[i*2], diff[i*2+1], (cnt[i*2] && cnt[i*2+1]) ? (lv[i*2+1] - rv[i*2] - 1) : 0});
}
void init(int i, int l, int r){
if(l==r){
cnt[i] = 0;
lv[i] = INF, rv[i] = 0, diff[i] = 0;
return;
}
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
merge(i);
}
void update(int i, int l, int r, int x, int v){
if(l==r){
cnt[i] += v;
if(!cnt[i]) lv[i] = INF, rv[i] = 0, diff[i] = 0;
else lv[i] = rv[i] = vy[l-1], diff[i] = 0;
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
merge(i);
}
} difftree;
void renumber(){
vx = vector<ll> (X+1, X+k+1);
vy = vector<ll> (Y+1, Y+k+1);
sort(vx.begin(), vx.end());
vx.erase(unique(vx.begin(), vx.end()), vx.end());
sort(vy.begin(), vy.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
sx = (int)vx.size(), sy = (int)vy.size();
for(int i=1; i<=k; i++){
rx[i] = lower_bound(vx.begin(), vx.end(), X[i]) - vx.begin() + 1;
ry[i] = lower_bound(vy.begin(), vy.end(), Y[i]) - vy.begin() + 1;
}
}
pair<ll, int> dqL[1002], dqR[1002], dqLen[1002];
int l1, l2, r1, r2, len1, len2;
int main(){
scanf("%lld %lld %d", &n, &m, &k);
// n=m=1000000000, k=300;
for(int i=1; i<=k; i++){
scanf("%lld %lld", &X[i], &Y[i]);
// X[i] = Y[i] = i*i+i+2;
}
renumber();
vector<ll> udlength (1, n-1); /// ����Ǵ� ������
for(int i=1; i<=k; i++){
udlength.push_back(X[i] - 1);
udlength.push_back(n - X[i]);
for(int j=1; j<=k; j++){
if(X[i] < X[j]) udlength.push_back(X[j] - X[i] - 1);
udlength.push_back(X[i] + n - X[j] - 1);
}
}
sort(udlength.begin(), udlength.end());
udlength.erase(unique(udlength.begin(), udlength.end()), udlength.end());
for(ll ud: udlength){ /// �� - �Ʒ� ����
if(ud<0) continue;
for(int i=1; i<=k; i++){
vec[i*2-2] = Event(X[i], ry[i], 1);
vec[i*2-1] = Event(X[i]+ud+1, ry[i], -1);
}
sort(vec, vec+k+k);
vector<Interval> info;
difftree.init(1, 1, sy);
bool bad = 0;
for(int s=0; s<k+k; s++){
int e = s;
while(e+1 < k+k && vec[e+1].x == vec[s].x) e++;
if(e+1 == k+k) break;
/// [s, e] ���� �������� ó��
for(int i=s; i<=e; i++){
if(vec[i].v == 1) difftree.update(1, 1, sy, vec[i].y, 1);
else difftree.update(1, 1, sy, vec[i].y, -1);
}
/// ��� ������ �Ѿ
if(difftree.cnt[1] == 0){
bad = 1;
break;
}
info.push_back(Interval(vec[s].x, vec[e+1].x-1, difftree.lv[1] - 1, m - difftree.rv[1], difftree.diff[1]));
s = e;
}
if(bad || info.empty()) continue;
deque<pair<ll, int> > dqL, dqR, dqLen;
int j = 0;
l1 = l2 = r1 = r2 = len1 = len2 = 0;
dqL[l2++] = make_pair(info[0].ldist, 0);
dqR[r2++] = make_pair(info[0].rdist, 0);
dqLen[len2++] = make_pair(info[0].mdist, 0);
for(int i=0; i<(int)info.size(); i++){
if(l1!=l2 && dqL[l1].second < i) l1++;
if(r1!=r2 && dqR[r1].second < i) r2++;
if(len1!=len2 && dqLen[len1].second < i) len1++;
while(j < (int)info.size() && info[j].r - info[i].l + 1 < n){
j++;
while(l1!=l2 && dqL[l2-1].first <= info[j].ldist) l2--;
dqL[l2++] = make_pair(info[j].ldist, j);
while(r1!=r2 && dqR[r2-1].first <= info[j].rdist) r2--;
dqR[r2++] = make_pair(info[j].rdist, j);
while(len1!=len2 && dqLen[l2-1].first <= info[j].mdist) l2--;
dqLen[len2++] = make_pair(info[j].mdist, j);
}
if(j == (int)info.size()) break;
ll minL = dqL[l1].first, minR = dqR[r1].first, len = dqLen[len1].first;
ans = min(ans, ud + max(len, minL+minR));
}
}
printf("%lld", ans);
}
Compilation message
cultivation.cpp: In function 'int main()':
cultivation.cpp:89:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld %lld %d", &n, &m, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
92 | scanf("%lld %lld", &X[i], &Y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
