제출 #1213658

#제출 시각아이디문제언어결과실행 시간메모리
1213658mychecksedadGarden (JOI23_garden)C++20
0 / 100
302 ms19552 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> // #pragma GCC optimize("O3,unroll-loops") // #pragma GCC target("avx2,bmi,bmi2") using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> #define cerr if(false) cerr const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, m, D, mx[N], L[N], R[N]; array<int, 2> a[N], b[N], c[N]; vector<int> cnt(N), V(N, -1); void add(int y, int idx){ cnt[y]++; V[y] = idx; // only the last one is important } void del(int y){ cnt[y]--; } void process(){ int cur = 0, last = -1, mn = MOD; for(int i = 0; i < D; ++i){ cerr << cnt[i] << ' '; if(cnt[i]){ if(mn == MOD) mn = i; if(last != -1){ cur = max(cur, i - last); } last = i; } } cerr << '\n'; cur = max(cur, mn + D - last); mx[0] = cur - 1; cerr << mn << ' ' << last<< ' ' << mx[0] << " f\n"; // mx[i] = pt=1...i is popped, what's the answer vector<pii> Q; for(int i = 0; i < D; ++i) if(V[i] != -1) Q.pb({i - D, V[i]}); for(int i = 0; i < D; ++i){ if(V[i] != -1){ while(Q.size() && Q.back().ss < V[i]) Q.pop_back(); if(Q.size()){ L[i] = Q.back().ff; }else assert(false); Q.pb({i, V[i]}); } } Q.clear(); for(int i = D-1; i >= 0; --i) if(V[i] != -1) Q.pb({i + D, V[i]}); for(int i = D-1; i >= 0; --i){ if(V[i] != -1){ while(Q.size() && Q.back().ss < V[i]) Q.pop_back(); if(Q.size()){ R[i] = Q.back().ff; }else assert(false); Q.pb({i, V[i]}); } } for(int i = 1; i <= D; ++i) mx[i] = -1; for(int i = 0; i < D; ++i) cerr << V[i] << ' '<< L[i] << ' ' << R[i] << '\n'; for(int i = 0; i < D; ++i) if(V[i] >= 0 && V[i] < MOD) mx[V[i]] = max(mx[V[i]], R[i] - L[i] - 1); for(int i = 1; i <= D; ++i) mx[i] = max(mx[i], mx[i - 1]); } void solve(){ cin >> n >> m >> D; for(int i = 1; i <= n; ++i){ cin >> a[i][0] >> a[i][1]; c[i] = {a[i][1], a[i][0]}; } for(int i = 1; i <= m; ++i){ cin >> b[i][0] >> b[i][1]; } sort(a+1, a+1+n); sort(c+1, c+1+n); sort(b+1, b+1+m); vi A; for(int i = 1; i <= n; ++i){ if(i == 1 || c[i - 1][0] != c[i][0]){ A.pb(c[i][0]); } } // add(c[1][0] + D, 0); // A.pb(c[1][0] + D); int R = a[n][0]; int ptr = 1; int ans = D * D; int ptr2 = 1; vector<deque<int>> Y(D); // y position of B's for(int i = 1; i <= m; ++i) Y[b[i][1]].pb(b[i][0]); for(int l = 0; l < D; ++l){ while(ptr <= n && l > a[ptr][0]){ R = a[ptr][0] + D; ++ptr; } int r = R; // minimum right border basically cerr << l << ' ' << r << " :\n"; while(ptr2 <= m && l > b[ptr2][0]){ Y[b[ptr2][1]].pop_front(); b[ptr2 + m] = {b[ptr2][0] + D, b[ptr2][1]}; Y[b[ptr2][1]].pb(b[ptr2][0] + D); ++ptr2; } // we will try all type B's... for(int i = 0, pt = 1; i < D; ++i) if(Y[i].size() && Y[i].back() > r){ add(i, pt++); } for(int x: A) add(x, MOD); process(); ans = min(ans, (D - mx[0]) * (r - l + 1)); cerr << D-mx[0] << ' ' << (r - l + 1) << " hmm\n"; cerr << mx[0] << " hell\n"; // this is the TLE area... for(int i = 0, pt = 1; i < D; ++i) if(Y[i].size() && Y[i].back() > r){ ans = min(ans, (D - mx[pt++]) * (max(r, Y[i].back()) - l + 1)); } V.clear(); V.resize(D, -1); for(int i = ptr2; i < ptr2 + m; ++i) if(b[i][0] > r) del(b[i][1]); // currently all B's are horizontal } cout << ans; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#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...