# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1071524 |
2024-08-23T08:08:07 Z |
김은성(#11136) |
Cultivation (JOI17_cultivation) |
C++17 |
|
2000 ms |
1236 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1.557e18;
vector<pair<ll, ll> > points;
ll r, c;
vector<ll> crit;
ll loc[609], hic[609], gapc[609];
ll lotree[1<<11], hitree[1<<11], gaptree[1<<11];
void settree(int v, int l, int r){
if(l==r){
lotree[v] = loc[l];
hitree[v] = hic[l];
gaptree[v] = gapc[l];
}
else{
int mid = (l+r)/2;
settree(2*v, l, mid);
settree(2*v+1, mid+1, r);
lotree[v] = max(lotree[2*v], lotree[2*v+1]);
hitree[v] = max(hitree[2*v], hitree[2*v+1]);
gaptree[v] = max(gaptree[2*v], gaptree[2*v+1]);
}
}
tuple<ll, ll, ll> maxquery(int v, int l, int r, int s, int e){
if(e < l || r <s)
return make_tuple(-INF, -INF, -INF);
if(s<=l && r<=e)
return make_tuple(lotree[v], hitree[v], gaptree[v]);
int mid = (l+r)/2;
tuple<ll, ll, ll> lt = maxquery(2*v, l, mid, s, e), rt = maxquery(2*v+1, mid+1, r, s, e);
return make_tuple(max(get<0>(lt), get<0>(rt)), max(get<1>(lt), get<1>(rt)), max(get<2>(lt), get<2>(rt)));
}
void minc(ll rd, ll ru){
crit.clear();
for(auto [y, x]: points){
crit.push_back(y - rd);
crit.push_back(y + ru + 1);
}
crit.push_back(-INF);
crit.push_back(INF);
sort(crit.begin(), crit.end());
crit.erase(unique(crit.begin(), crit.end()), crit.end());
int sz = crit.size(), i, j;
vector<vector<ll> > add(sz), del(sz);
for(auto [y, x]: points){
int lo = lower_bound(crit.begin(), crit.end(), y - rd) - crit.begin();
int hi = lower_bound(crit.begin(), crit.end(), y + ru + 1) - crit.begin();
//printf("y=%lld lo=%d hi=%d\n", y, lo, hi);
add[lo].push_back(x);
del[hi].push_back(x);
}
ll cd = 0, cu = 0, sum = 0;
multiset<ll> s, gap;
for(i=0; i<sz; i++){
for(ll x: add[i]){
auto it = s.insert(x);
//printf("x=%lld s.size=%d\n", x, s.size());
if(it != s.begin()){
auto itl = --it;
it++;
gap.insert((*it) - (*itl));
auto itr = ++it;
it--;
if(itr != s.end()){
gap.insert((*itr) - (*it));
gap.erase(gap.find((*itr) - (*itl)));
}
}
else{
auto itr = ++it;
it--;
if(itr != s.end()){
gap.insert((*itr) - (*it));
}
}
}
for(ll x: del[i]){
auto itr = s.erase(s.find(x));
if(itr != s.end()){
gap.erase(gap.find((*itr) - x));
if(itr != s.begin()){
auto itl = --itr;
itr++;
gap.erase(gap.find(x - (*itl)));
gap.insert((*itr) - (*itl));
}
}
else if(itr != s.begin()){
auto itl = --itr;
gap.erase(gap.find(x - (*itl)));
}
}
if(s.empty()){
loc[i] = INF;
hic[i] = INF;
}
else{
loc[i] = *(s.begin()) - 1;
hic[i] = c - *(--s.end());
}
if(gap.empty())
gapc[i] = -1;
else
gapc[i] = *(--gap.end()) -1;
//printf("i=%d lo=%lld hi=%lld gap=%lld\n", i, loc[i], hic[i], gapc[i]);
}
settree(1, 0, sz-1);
}
int main(){
ll y, x, rd, ru;
int n, i, j;
scanf("%lld %lld %d", &r, &c, &n);
for(i=1; i<=n; i++){
scanf("%lld %lld", &y, &x);
points.push_back(make_pair(y, x));
}
vector<ll> critd, critu, critdu;
for(auto [y, x]: points){
critd.push_back(y - 1);
critu.push_back(r - y);
}
for(auto [y1, x1]: points){
for(auto [y2, x2]: points){
if(y2 > y1)
critdu.push_back(y2 - y1 - 1);
}
}
sort(critd.begin(), critd.end());
critd.erase(unique(critd.begin(), critd.end()), critd.end());
sort(critu.begin(), critu.end());
critu.erase(unique(critu.begin(), critu.end()), critu.end());
sort(critdu.begin(), critdu.end());
critdu.erase(unique(critdu.begin(), critdu.end()), critdu.end());
ll ans = INF;
for(auto rd: critd){
for(auto ru: critu){
minc(0, rd+ru);
int lo = upper_bound(crit.begin(), crit.end(), rd+1) - crit.begin() - 1;
int hi = upper_bound(crit.begin(), crit.end(), rd+r) - crit.begin() - 1;
tuple<ll, ll, ll> ret = maxquery(1, 0, (int)crit.size() -1, lo, hi);
//printf("rd=%lld ru=%lld ret=%lld\n", rd, ru, rd+ru+max(get<0>(ret)+get<1>(ret), get<2>(ret)));
//printf("lo=%lld hi=%lld gap=%lld\n", get<0>(ret), get<1>(ret), get<2>(ret));
ans = min(ans, rd+ru+max(get<0>(ret)+get<1>(ret), get<2>(ret)));
}
}
for(auto temp: critdu){
minc(0, temp);
for(auto rd: critd){
if(temp - rd < 0)
continue;
int lo = upper_bound(crit.begin(), crit.end(), rd+1) - crit.begin() - 1;
int hi = upper_bound(crit.begin(), crit.end(), rd+r) - crit.begin() - 1;
tuple<ll, ll, ll> ret = maxquery(1, 0, (int)crit.size() -1, lo, hi);
//printf("rd=%lld ru=%lld ret=%lld\n", rd, temp-rd, temp+max(get<0>(ret)+get<1>(ret), get<2>(ret)));
ans = min(ans, temp + max(get<0>(ret)+get<1>(ret), get<2>(ret)));
}
for(auto ru: critu){
ll rd = temp - ru;
if(rd < 0)
continue;
int lo = upper_bound(crit.begin(), crit.end(), rd+1) - crit.begin() - 1;
int hi = upper_bound(crit.begin(), crit.end(), rd+r) - crit.begin() - 1;
tuple<ll, ll, ll> ret = maxquery(1, 0, (int)crit.size() -1, lo, hi);
//printf("rd=%lld ru=%lld ret=%lld\n", rd, ru, rd+ru+max(get<0>(ret)+get<1>(ret), get<2>(ret)));
ans = min(ans, temp + max(get<0>(ret)+get<1>(ret), get<2>(ret)));
}
}
printf("%lld\n", ans);
return 0;
}
Compilation message
cultivation.cpp: In function 'void minc(ll, ll)':
cultivation.cpp:44:27: warning: unused variable 'j' [-Wunused-variable]
44 | int sz = crit.size(), i, j;
| ^
cultivation.cpp:53:5: warning: unused variable 'cd' [-Wunused-variable]
53 | ll cd = 0, cu = 0, sum = 0;
| ^~
cultivation.cpp:53:13: warning: unused variable 'cu' [-Wunused-variable]
53 | ll cd = 0, cu = 0, sum = 0;
| ^~
cultivation.cpp:53:21: warning: unused variable 'sum' [-Wunused-variable]
53 | ll cd = 0, cu = 0, sum = 0;
| ^~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:111:11: warning: unused variable 'rd' [-Wunused-variable]
111 | ll y, x, rd, ru;
| ^~
cultivation.cpp:111:15: warning: unused variable 'ru' [-Wunused-variable]
111 | ll y, x, rd, ru;
| ^~
cultivation.cpp:112:12: warning: unused variable 'j' [-Wunused-variable]
112 | int n, i, j;
| ^
cultivation.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%lld %lld %d", &r, &c, &n);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
cultivation.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
115 | scanf("%lld %lld", &y, &x);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
15 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
388 KB |
Output is correct |
21 |
Correct |
20 ms |
348 KB |
Output is correct |
22 |
Correct |
86 ms |
568 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
146 ms |
728 KB |
Output is correct |
25 |
Correct |
104 ms |
604 KB |
Output is correct |
26 |
Correct |
276 ms |
984 KB |
Output is correct |
27 |
Correct |
248 ms |
980 KB |
Output is correct |
28 |
Correct |
152 ms |
728 KB |
Output is correct |
29 |
Correct |
218 ms |
980 KB |
Output is correct |
30 |
Correct |
240 ms |
984 KB |
Output is correct |
31 |
Correct |
240 ms |
984 KB |
Output is correct |
32 |
Correct |
230 ms |
984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
15 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
388 KB |
Output is correct |
21 |
Correct |
20 ms |
348 KB |
Output is correct |
22 |
Correct |
86 ms |
568 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
146 ms |
728 KB |
Output is correct |
25 |
Correct |
104 ms |
604 KB |
Output is correct |
26 |
Correct |
276 ms |
984 KB |
Output is correct |
27 |
Correct |
248 ms |
980 KB |
Output is correct |
28 |
Correct |
152 ms |
728 KB |
Output is correct |
29 |
Correct |
218 ms |
980 KB |
Output is correct |
30 |
Correct |
240 ms |
984 KB |
Output is correct |
31 |
Correct |
240 ms |
984 KB |
Output is correct |
32 |
Correct |
230 ms |
984 KB |
Output is correct |
33 |
Correct |
2 ms |
856 KB |
Output is correct |
34 |
Correct |
191 ms |
984 KB |
Output is correct |
35 |
Correct |
260 ms |
980 KB |
Output is correct |
36 |
Correct |
267 ms |
980 KB |
Output is correct |
37 |
Correct |
195 ms |
980 KB |
Output is correct |
38 |
Correct |
261 ms |
984 KB |
Output is correct |
39 |
Correct |
254 ms |
980 KB |
Output is correct |
40 |
Correct |
258 ms |
984 KB |
Output is correct |
41 |
Correct |
76 ms |
860 KB |
Output is correct |
42 |
Correct |
196 ms |
984 KB |
Output is correct |
43 |
Correct |
249 ms |
1236 KB |
Output is correct |
44 |
Correct |
258 ms |
980 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
8 ms |
480 KB |
Output is correct |
3 |
Correct |
9 ms |
348 KB |
Output is correct |
4 |
Correct |
8 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
476 KB |
Output is correct |
6 |
Correct |
7 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
476 KB |
Output is correct |
8 |
Correct |
8 ms |
476 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
9 ms |
476 KB |
Output is correct |
11 |
Correct |
9 ms |
348 KB |
Output is correct |
12 |
Correct |
10 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
5 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
480 KB |
Output is correct |
17 |
Correct |
9 ms |
348 KB |
Output is correct |
18 |
Correct |
6 ms |
348 KB |
Output is correct |
19 |
Correct |
9 ms |
476 KB |
Output is correct |
20 |
Correct |
7 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
348 KB |
Output is correct |
2 |
Correct |
8 ms |
480 KB |
Output is correct |
3 |
Correct |
9 ms |
348 KB |
Output is correct |
4 |
Correct |
8 ms |
348 KB |
Output is correct |
5 |
Correct |
9 ms |
476 KB |
Output is correct |
6 |
Correct |
7 ms |
348 KB |
Output is correct |
7 |
Correct |
2 ms |
476 KB |
Output is correct |
8 |
Correct |
8 ms |
476 KB |
Output is correct |
9 |
Correct |
4 ms |
348 KB |
Output is correct |
10 |
Correct |
9 ms |
476 KB |
Output is correct |
11 |
Correct |
9 ms |
348 KB |
Output is correct |
12 |
Correct |
10 ms |
348 KB |
Output is correct |
13 |
Correct |
2 ms |
348 KB |
Output is correct |
14 |
Correct |
3 ms |
348 KB |
Output is correct |
15 |
Correct |
5 ms |
348 KB |
Output is correct |
16 |
Correct |
9 ms |
480 KB |
Output is correct |
17 |
Correct |
9 ms |
348 KB |
Output is correct |
18 |
Correct |
6 ms |
348 KB |
Output is correct |
19 |
Correct |
9 ms |
476 KB |
Output is correct |
20 |
Correct |
7 ms |
348 KB |
Output is correct |
21 |
Correct |
481 ms |
560 KB |
Output is correct |
22 |
Correct |
642 ms |
348 KB |
Output is correct |
23 |
Correct |
543 ms |
556 KB |
Output is correct |
24 |
Correct |
548 ms |
344 KB |
Output is correct |
25 |
Correct |
647 ms |
556 KB |
Output is correct |
26 |
Correct |
266 ms |
348 KB |
Output is correct |
27 |
Correct |
529 ms |
348 KB |
Output is correct |
28 |
Correct |
653 ms |
596 KB |
Output is correct |
29 |
Correct |
625 ms |
560 KB |
Output is correct |
30 |
Correct |
641 ms |
348 KB |
Output is correct |
31 |
Correct |
635 ms |
560 KB |
Output is correct |
32 |
Correct |
614 ms |
348 KB |
Output is correct |
33 |
Correct |
389 ms |
596 KB |
Output is correct |
34 |
Correct |
607 ms |
348 KB |
Output is correct |
35 |
Correct |
609 ms |
560 KB |
Output is correct |
36 |
Correct |
548 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
0 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
600 KB |
Output is correct |
11 |
Correct |
1 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
1 ms |
348 KB |
Output is correct |
17 |
Correct |
1 ms |
344 KB |
Output is correct |
18 |
Correct |
15 ms |
348 KB |
Output is correct |
19 |
Correct |
4 ms |
348 KB |
Output is correct |
20 |
Correct |
1 ms |
388 KB |
Output is correct |
21 |
Correct |
20 ms |
348 KB |
Output is correct |
22 |
Correct |
86 ms |
568 KB |
Output is correct |
23 |
Correct |
3 ms |
348 KB |
Output is correct |
24 |
Correct |
146 ms |
728 KB |
Output is correct |
25 |
Correct |
104 ms |
604 KB |
Output is correct |
26 |
Correct |
276 ms |
984 KB |
Output is correct |
27 |
Correct |
248 ms |
980 KB |
Output is correct |
28 |
Correct |
152 ms |
728 KB |
Output is correct |
29 |
Correct |
218 ms |
980 KB |
Output is correct |
30 |
Correct |
240 ms |
984 KB |
Output is correct |
31 |
Correct |
240 ms |
984 KB |
Output is correct |
32 |
Correct |
230 ms |
984 KB |
Output is correct |
33 |
Correct |
2 ms |
856 KB |
Output is correct |
34 |
Correct |
191 ms |
984 KB |
Output is correct |
35 |
Correct |
260 ms |
980 KB |
Output is correct |
36 |
Correct |
267 ms |
980 KB |
Output is correct |
37 |
Correct |
195 ms |
980 KB |
Output is correct |
38 |
Correct |
261 ms |
984 KB |
Output is correct |
39 |
Correct |
254 ms |
980 KB |
Output is correct |
40 |
Correct |
258 ms |
984 KB |
Output is correct |
41 |
Correct |
76 ms |
860 KB |
Output is correct |
42 |
Correct |
196 ms |
984 KB |
Output is correct |
43 |
Correct |
249 ms |
1236 KB |
Output is correct |
44 |
Correct |
258 ms |
980 KB |
Output is correct |
45 |
Correct |
2 ms |
348 KB |
Output is correct |
46 |
Correct |
8 ms |
480 KB |
Output is correct |
47 |
Correct |
9 ms |
348 KB |
Output is correct |
48 |
Correct |
8 ms |
348 KB |
Output is correct |
49 |
Correct |
9 ms |
476 KB |
Output is correct |
50 |
Correct |
7 ms |
348 KB |
Output is correct |
51 |
Correct |
2 ms |
476 KB |
Output is correct |
52 |
Correct |
8 ms |
476 KB |
Output is correct |
53 |
Correct |
4 ms |
348 KB |
Output is correct |
54 |
Correct |
9 ms |
476 KB |
Output is correct |
55 |
Correct |
9 ms |
348 KB |
Output is correct |
56 |
Correct |
10 ms |
348 KB |
Output is correct |
57 |
Correct |
2 ms |
348 KB |
Output is correct |
58 |
Correct |
3 ms |
348 KB |
Output is correct |
59 |
Correct |
5 ms |
348 KB |
Output is correct |
60 |
Correct |
9 ms |
480 KB |
Output is correct |
61 |
Correct |
9 ms |
348 KB |
Output is correct |
62 |
Correct |
6 ms |
348 KB |
Output is correct |
63 |
Correct |
9 ms |
476 KB |
Output is correct |
64 |
Correct |
7 ms |
348 KB |
Output is correct |
65 |
Correct |
481 ms |
560 KB |
Output is correct |
66 |
Correct |
642 ms |
348 KB |
Output is correct |
67 |
Correct |
543 ms |
556 KB |
Output is correct |
68 |
Correct |
548 ms |
344 KB |
Output is correct |
69 |
Correct |
647 ms |
556 KB |
Output is correct |
70 |
Correct |
266 ms |
348 KB |
Output is correct |
71 |
Correct |
529 ms |
348 KB |
Output is correct |
72 |
Correct |
653 ms |
596 KB |
Output is correct |
73 |
Correct |
625 ms |
560 KB |
Output is correct |
74 |
Correct |
641 ms |
348 KB |
Output is correct |
75 |
Correct |
635 ms |
560 KB |
Output is correct |
76 |
Correct |
614 ms |
348 KB |
Output is correct |
77 |
Correct |
389 ms |
596 KB |
Output is correct |
78 |
Correct |
607 ms |
348 KB |
Output is correct |
79 |
Correct |
609 ms |
560 KB |
Output is correct |
80 |
Correct |
548 ms |
344 KB |
Output is correct |
81 |
Execution timed out |
2061 ms |
728 KB |
Time limit exceeded |
82 |
Halted |
0 ms |
0 KB |
- |