Submission #1213208

#TimeUsernameProblemLanguageResultExecution timeMemory
1213208mychecksedadGarden (JOI23_garden)C++20
0 / 100
682 ms46744 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> 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> const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, m, D; array<int, 2> a[N], b[N]; multiset<int> Y, dif; // Y's of type A's and differences void add(int y){ auto it = Y.lower_bound(y); if(it != Y.begin()){ dif.insert(y - (*prev(it))); } if(it != Y.end()){ dif.insert((*it) - y); } if(it != Y.begin() && it != Y.end()){ dif.erase(dif.find((*it) - (*prev(it)))); } Y.insert(y); } void del(int y){ auto it = Y.lower_bound(y); if(it != Y.begin()){ dif.erase(dif.find(y - (*prev(it)))); } if(next(it) != Y.end()){ dif.erase(dif.find((*next(it)) - y)); } if(it != Y.begin() && next(it) != Y.end()){ dif.insert((*next(it)) - (*prev(it))); } Y.erase(it); } int get_max(){ return max((*prev(dif.end())), (*Y.begin()) + D - (*prev(Y.end()))) - 1; // 2 constant factor gone } void solve(){ cin >> n >> m >> D; for(int i = 1; i <= n; ++i){ cin >> a[i][0] >> a[i][1]; } for(int i = 1; i <= m; ++i){ cin >> b[i][0] >> b[i][1]; } sort(a+1, a+1+n); sort(b+1, b+1+m); for(int i = 1; i <= n; ++i){ if(i == 1 || a[i - 1][1] != a[i][1]){ add(a[i][1]); } } int R = a[n][0]; int ptr = 1; int ans = D * D; int ptr2 = 1; 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]){ b[ptr2 + m] = {b[ptr2][0] + D, b[ptr2][1]}; ++ptr2; } // for(int i = ptr2; i < ptr2 + m; ++i) cerr << b[i][0] << ' ' << b[i][1] << '\n'; // cerr << '\n'; // we will try all type B's... for(int i = ptr2; i < m + ptr2; ++i){ if(b[i][0] > r) add(b[i][1]); // let's assume we're taking them all horizontal } ans = min(ans, (D - get_max()) * (r - l + 1)); // cerr << "ans: " << (D - get_max()) * (r - l + 1) << '\n'; for(int i = ptr2; i < ptr2 + m; ++i){ if(b[i][0] > r){ del(b[i][1]); // erase em' one by one } ans = min(ans, (D - get_max()) * (max(r, b[i][0]) - l + 1)); } } 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...