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 <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int dmax = 5e3 + 5, nmax = 5e5 + 5;
int D;
namespace DS { // lista dubla
#define prev mata
#define next tactu
int prev[dmax], next[dmax];
int mx;
void init(int d) {
for(int i = 1; i < d; i++) prev[i] = i - 1;
prev[0] = d - 1;
for(int i = 0; i < d - 1; i++) next[i] = i + 1;
next[d - 1] = 0;
mx = 1;
}
void Insert(int x) {
//cerr << "inserting: " << x << " -> " << prev[x] << " = " << (x - prev[x] + D) % D << '\n';
if(prev[x] == x) mx = max(mx, D);
else mx = max(mx, (x - prev[x] + D) % D);
}
void Erase(int x) {
return;
}
void erasepoz(int x) {
//cerr << "erasing " << x << ' ' << prev[9] << ' ' << next[9] << '\n';
int r = next[x], l = prev[x];
prev[r] = l;
next[l] = r;
Insert(r);
Insert(l);
}
int query() {
return D - mx + 1;
}
#undef prev
#undef next
}
int whichtype[dmax];
using T = int;
T blablalba[dmax][dmax];
T blablalba2[dmax][dmax];
T& prv1(int x, int y) { return blablalba[y][x]; }
T& prv2(int x, int y) { return blablalba2[y][x]; }
vector<pii> toerase[dmax];
int remain[dmax];
signed main() {
cin.tie(0) -> sync_with_stdio(0);
int n, m, d;
cin >> n >> m >> d;
D = d;
for(int i = 0; i < d; i++) whichtype[i] = 0;
for(int i = 0, x, y; i < n; i++) {
cin >> x >> y;
swap(x, y);
whichtype[y] |= 1;
prv1(x, y) = 1;
}
for(int i = 0, x, y; i < m; i++) {
cin >> x >> y;
swap(x, y);
prv2(x, y) = 1;
whichtype[y] |= 2;
}
{
for(int i = 0; i < d; i++) {
if((whichtype[i] & 1) == 0) continue;
int p = d - 1;
while(prv1(p, i) == 0) p--;
for(int j = 0; j < d; j++) {
int u = prv1(j, i);
prv1(j, i) = p;
if(u == 1) p = j;
}
}
for(int i = 0; i < d; i++) {
if((whichtype[i] & 2) == 0) continue;
int p = d - 1;
while(prv2(p, i) == 0) p--;
for(int j = 0; j < d; j++) {
int u = prv2(j, i);
prv2(j, i) = p;
if(u == 1) p = j;
}
}
}
int mn = d * d;
for(int upperline = 0; upperline < d; upperline++) {
//cerr << "------------\n";
DS::init(d);
int cnt = 0;
for(int i = 0; i < d; i++) toerase[i].clear();
for(int j = 0; j < d; j++) {
remain[j] = whichtype[j];
if(whichtype[j] == 0) { DS::erasepoz(j); continue; }
//cerr << j << ": " << (int)prv1(upperline, j) << ' ';
if((whichtype[j] & 1) == 1)
toerase[prv1(upperline, j)].emplace_back(j, 1), cnt++;
if((whichtype[j] & 2) == 2)
toerase[prv2(upperline, j)].emplace_back(j, 2);
}
//cerr << '\n';
for(int lowerline = upperline, timp = 1; timp <= d; timp++, lowerline = (lowerline + 1) % d) {
for(auto [col, val] : toerase[lowerline]) {
if(val == 1) cnt--;
else remain[col] ^= val;
if(remain[col] == 0) DS::erasepoz(col);
}
//cerr << upperline << ' ' << lowerline << '\t' << DS::query() << ' ' << cnt << '\t' << DS::query() * timp << '\n';
if(cnt == 0) mn = min(mn, timp * DS::query());
}
}
cout << mn << '\n';
}
/**
Anul asta se da centroid.
-- Surse oficiale
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |