(UPD: 2024-12-04 14:48 UTC) Judge is not working due to Cloudflare incident. (URL) We can do nothing about it, sorry. After the incident is resolved, we will grade all submissions.

Submission #830775

#TimeUsernameProblemLanguageResultExecution timeMemory
830775vjudge1Garden (JOI23_garden)C++17
100 / 100
1012 ms108704 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...