| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 881145 | eitanelb | Cultivation (JOI17_cultivation) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<string>
#include<fstream>
#include "frogs.h"
using namespace std;
#include<vector>
#include<iostream>
#include<set>
#include<algorithm>
#include "frogs.h"
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
/*
for down - just real distances from down (optional also for left) -> O(n)
for up - just real distances, or such that together it's distance between two -> O(n)+O(n^2)
after I have up and down - O(n^2) //optional - O(nlogu), with segmentree sparse/coordination, then O(n^4 logU)
then O(n^5), or if r<=40 -> O(40*40*40*n)
which is 60 points
for 100 points, let's see that whenever you get the up bigger, it affects only one place
that can being it to O(n^3), which is 100 points
*/
int deb = 1;
pair<int, pi>* merge(pair<int, pi>* v1, pair<int, pi>* v2, int n1, int n2) {
pair<int, pi>* v3 = new pair<int,pi>[n1+n2];
int p1 = 0, p2 = 0, p3=0;
while (p1 < n1 || p2 < n2) {
if (p1 != n1 && (p2 == n2 || v1[p1].x <= v2[p2].x)) v3[p3++] = v1[p1++];
else v3[p3++] = v2[p2++];
}
return v3;
}
int Time_To_Fool_The_Lab(int r, int c, int n, vector<int> X, vector<int> Y) {
int* vdown = new int[n];
pair<int, pi>* vup = new pair<int, pi>[n];
int sz = n * (n - 1) / 2;
pair<int, pi>* vsum = new pair<int, pi>[sz];
int t = 0;
for (int i = 0; i < n; i++) {
vdown[i] = X[i] - 1;
}
for (int i = 0; i < n; i++) {
vup[i] = {r - X[i], {i, -1}};
for (int j = 0; j < n; j++) if (X[i] > X[j]) vsum[t++]={X[i] - X[j] - 1, {i, j}};
}
sort(vup, vup+n);
sort(vsum, vsum + sz);
int res = 2e9;
for (int d = 0; d < n; d++) {
int down = vdown[d];
pair<int, pi>* vnup = new pair<int, pi>[sz];
for (int i = 0; i < sz;i++) vnup[i] = {vsum[i].x - down,vsum[i].y};
vnup = merge(vnup, vup,sz,n);
bool* on = new bool[n];
int *dr=new int[n], * dl = new int[n], * maxi = new int[n], * disl = new int[n], * disr = new int[n];
for (int i = 0; i < n; i++) {
on[i] = 0;
if (X[i] == r) {
dr[i] = dl[i] = 0;
continue;
}
dr[i] = c - Y[i];
dl[i] = Y[i] - 1;
disl[i] = disr[i] = c;
for (int j = 0; j < n; j++) {
if (j == i) continue;
if (X[j] > X[i] && X[j] - down <= X[i] + 1) {
if (Y[j] > Y[i]) dr[i] = min(dr[i], Y[j] - Y[i] - 1);
else if (Y[j] < Y[i]) dl[i] = min(dl[i], Y[i] - Y[j] - 1);
else on[i] = 1;
disr[i] = min(disr[i], c - Y[j]);
disl[i] = min(disl[i], Y[j]-1);
}
}
}
multiset<int> maxs, sdl, sdr;
for (int i = 0; i < n; i++) {
if (on[i]) maxi[i] = max(dr[i], dl[i]);
else maxi[i] = dr[i] + dl[i] + 1;
maxs.insert(maxi[i]);
sdl.insert(disl[i]);
sdr.insert(disr[i]);
}
if (deb) {for (int i = 0; i < n; i++) {cout << dl[i] << ' ' << dr[i] << ' ' << maxi[i] << ' ' << on[i] << endl;}}
// row 1 ************
int mx1 = 0;
set<int> st;
for (int i = 0; i < n; i++)
if (X[i] - down <= 1)
st.insert(Y[i]);
sdl.insert(*st.begin() - 1);
sdr.insert(c - *prev(st.end()));
int fr = 0;
for (int i : st) {
mx1 = max(mx1, i - fr - 1);
fr = i;
}
maxs.insert(mx1);
int up = 0;
for (int q = 0; q < (n + sz);q++) {
pair<int, pi> pr = vnup[q];
up = pr.x;
if (up < 0) continue;
if (pr.y.y == -1) {
int u = pr.y.x;
maxs.erase(maxs.find(maxi[u]));
sdl.erase(sdl.find(disl[u]));
sdr.erase(sdr.find(disr[u]));
maxi[u] = dr[u] = dl[u] = disr[u] = disl[u] = 0;
maxs.insert(0); sdl.insert(0); sdr.insert(0);
}
else {
int i = pr.y.x, j = pr.y.y;
if (Y[i]== Y[j]) on[j] = 1;
else if (Y[i] > Y[j]) {
if (dr[j] > Y[i] - Y[j] - 1) {
dr[j] = Y[i] - Y[j] - 1;
}
}
else {
if (dl[j] > Y[j] - Y[i] - 1) {
dl[j] = Y[j] - Y[i] - 1;
}
}
sdl.erase(sdl.find(disl[j]));
sdr.erase(sdr.find(disr[j]));
disr[j] = min(disr[j], c - Y[i]);
disl[j] = min(disl[j], Y[i] - 1);
sdl.insert(disl[j]);
sdr.insert(disr[j]);
maxs.erase(maxs.find(maxi[j]));
if (on[j]) maxi[j] = max(dr[j], dl[j]);
else maxi[j] = dr[j] + dl[j] + 1;
maxs.insert(maxi[j]);
}
int mxla=*prev(sdl.end()), mxfa = *prev(sdr.end());
int mx = *prev(maxs.end());
if (mxla >= c || mxfa >= c) continue;
mx = max(mx, mxla + mxfa);
if (mx > 2e9 - up - down) continue;
res = min(res, mx + down + up);
}
}
return res;
}
int run = 1;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
if (run == 1) {
int R, C, N;
cin >> R >> C >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
cin >> X[i] >> Y[i];
}
int res = Time_To_Fool_The_Lab(R, C, N, X, Y);
cout << res << endl;
}
if (run == 2) {
vector<int> sizes = {0, 16, 16, 12, 20, 16, 3 };
string name = "01-01";
for(int j=1;j<2;j++){
cout << "****" << j << "****\n";
name[1] = '0' + j;
for (int i = 13; i <= sizes[j]; i++) {
cout << "**" << j << ' ' << i << "**\n";
name[3] = '0' + i / 10; name[4] = '0' + i % 10;
ifstream fin(name + ".in"), fout(name + ".out");
int R, C, N;
fin >> R >> C >> N;
vector<int> X(N), Y(N);
for (int i = 0; i < N; i++) {
fin >> X[i] >> Y[i];
}
int nres, res = Time_To_Fool_The_Lab(R, C, N, X, Y);
fout >> nres;
if (nres != res) {
cout << "subtask " << j << "test" << i << endl;
cout << R << ' ' << C << endl << N << endl;
for (int i = 0; i < N; i++) {
cout << X[i] << ' ' << Y[i] << endl;
}
cout << res << ' ' << nres << endl;
break;
}
}
}
}
}