#include <bits/stdc++.h>
#pragma optimize("O3, unroll-loops")
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 307, inf = 2e9;
int n, m, k;
int a[N], b[N];
int mem[2*N][N];
pii gr[2*N][N];
vector <int> add[2*N], rem[2*N];
struct MQ {
queue <ll> q; deque <ll> dq;
inline void push(ll x) {q.push(x); while (!dq.empty() && dq.back() < x) dq.pop_back(); dq.pb(x);}
inline void pop() {ll x = q.front(); q.pop(); if (dq[0] == x) dq.pop_front();}
inline ll get() {return dq[0];}
};
int main () {
FIO;
cin >> n >> m >> k;
vector <pii> so;
for (int i = 0; i < k; i++) {
cin >> a[i] >> b[i];
a[i]--; b[i]--;
so.pb({a[i], b[i]});
}
sort(all(so));
for (int i = 0; i < k; i++) a[i] = so[i].F, b[i] = so[i].S;
int d = a[0]; for (int i = 0; i < k; i++) a[i] -= d;
d = n-a[k-1]-1; for (int i = 1; i < k; i++) d = max(d, a[i]-a[i-1]-1);
a[k] = n-1;
vector <ll> v; v.pb(d);
for (int i = 0; i <= k; i++) {
for (int j = i; j <= k; j++) {
if (a[j]-a[i] >= d) v.pb(a[j]-a[i]);
if (a[j]-a[i]-1 >= d) v.pb(a[j]-a[i]-1);
if (a[j]+n-a[i]-1 >= d) v.pb(a[j]+n-a[i]-1);
if (a[i]+n-a[j]-1 >= d) v.pb(a[i]+n-a[j]-1);
}
if (n-a[i]-1 >= d) v.pb(n-a[i]-1);
}
sort(all(v)); v.erase(unique(all(v)), v.end());
//PRECOMPUTE -> O(N^2 log N)
for (int i = 0; i < k; i++) {
set <int> s;
multiset <int> rj;
rj.insert(0);
for (int j = i; j >= 0; j--) {
mem[i][j] = mem[i][j+1];
gr[i][j].F = gr[i][j+1].F;
gr[i][j].S = gr[i][j+1].S;
if (s.find(b[j]) != s.end()) continue;
auto p1 = s.lower_bound(b[j]);
if (p1 == s.end()) {
if (!s.empty()) rj.insert(b[j]-*(--p1)-1);
s.insert(b[j]);
gr[i][j] = {*s.begin(), m-*s.rbegin()-1};
}
else if (p1 == s.begin()) {
rj.insert(*p1-b[j]-1);
s.insert(b[j]);
gr[i][j] = {*s.begin(), m-*s.rbegin()-1};
}
else {
int x = *p1; --p1; int y = *p1;
rj.erase(rj.find(x-y-1));
rj.insert(x-b[j]-1);
rj.insert(b[j]-y-1);
s.insert(b[j]);
}
mem[i][j] = *rj.rbegin();
}
}
//SOLVE O(N^3)
ll mn = inf;
for (auto x : v) {
MQ m1, m2, m3;
vector <pair <pii, ll> > vv;
int l = 0, r = -1, z = 0;
for (int i = 0; i < k; i++) {
while (a[z]+x < a[i]) {
if (vv.back().S != (ll)a[z]+x+1) {vv.pb({{l+1, r}, (ll)a[z]+x+1}); l++;}
else vv[vv.size()-1].F.F++;
z++;
}
if (vv.empty() || vv.back().S != a[i]) {vv.pb({{l, r+1}, a[i]}); r++;}
else vv[vv.size()-1].F.S++, r++;
}
while (z < k) {
if (vv.back().S != (ll)a[z]+x+1) {vv.pb({{l+1, r}, (ll)a[z]+x+1}); l++;}
else vv[vv.size()-1].F.F++, l++;
z++;
}
z = 0;
const ll oo = 1e18;
#define C (x+max(m1.get(), m2.get()+m3.get()))
for (int i = 0; i+1 < vv.size() && vv[i].S < 2*n; i++) {
l = vv[i].F.F;
r = vv[i].F.S;
m1.push(mem[r][l]); m2.push(gr[r][l].F); m3.push(gr[r][l].S);
while (vv[z].S+n-1 < vv[i+1].S) {
mn = min(mn, C);
m1.pop(); m2.pop(); m3.pop();
z++;
}
}
}
cout << mn << "\n";
return 0;
}
Compilation message
cultivation.cpp:3: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
3 | #pragma optimize("O3, unroll-loops")
|
cultivation.cpp: In function 'int main()':
cultivation.cpp:116:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
116 | for (int i = 0; i+1 < vv.size() && vv[i].S < 2*n; i++) {
| ~~~~^~~~~~~~~~~
cultivation.cpp:113:12: warning: unused variable 'oo' [-Wunused-variable]
113 | const ll oo = 1e18;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
604 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
624 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
600 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
2 ms |
604 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
624 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
