Submission #900582

#	Time	Username	Problem	Language	Result	Execution time	Memory
900582		qin	Garden (JOI23_garden)	C++17	30 / 100	3037 ms	35092 KiB

garden

#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n");
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18; int mod = 119<<23|1;
void answer(){
		int n, m, d;
		scanf("%d%d%d", &n, &m, &d);
		vector<vector<int>> t(d*2);
		for(int i = 1; i <= n; ++i){
				int a, b; scanf("%d%d", &a, &b);
				t[a].emplace_back(b), t[a+d].emplace_back(b);
		}
		for(int i = 0; i < d*2; ++i) sort(t[i].begin(), t[i].end());
		
		vector<vector<int>> x(d*2);
		vector<int> y(m+1);
		for(int i = 1; i <= m; ++i){
				int a, b; scanf("%d%d", &a, &b), y[i] = b;
				x[a].emplace_back(i), x[a+d].emplace_back(i);
		}
		int result = inf;
		for(int i = 0; i < d; ++i){
				multiset<int> a, b;
				for(int j = 0; j < d; ++j) for(int &u : x[j]) b.emplace(y[u]);
				for(int j = i; j < i+d; ++j){
						for(int &u : t[j]) a.emplace(u);
						for(int &u : x[j]) b.erase(b.lower_bound(y[u]));
						if(ssize(a) != n) continue;
						int mxa = *prev(a.end()), mxb = ssize(b) ? *prev(b.end()) : 0;
						for(int l = 0; l < d; ++l){
								if(!ssize(b)) mxb = l;
								//~ printf("%d %d: %d %d\n", i, j, l, max(mxa, mxb));
								result = min(result, (j-i+1)*(max(mxa, mxb)-l+1));
								auto it = a.lower_bound(l);
								if(it != a.end() && *it == l) mxa = max(mxa, l+d);
								it = b.lower_bound(l);
								if(it != b.end() && *it == l) mxb = max(mxb, l+d);
						}
				}
		}
		printf("%d\n", result);
}
signed main(){
		int T = 1;
		for(++T; --T; ) answer();
		return 0;
}

Compilation message (stderr)

garden.cpp: In function 'void answer()':
garden.cpp:12:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   scanf("%d%d%d", &n, &m, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
garden.cpp:15:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     int a, b; scanf("%d%d", &a, &b);
      |               ~~~~~^~~~~~~~~~~~~~~~
garden.cpp:23:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     int a, b; scanf("%d%d", &a, &b), y[i] = b;
      |               ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25