oj.uz

Submission #47320

# Submission time Handle Problem Language Result Execution time Memory
47320 2018-04-30T14:33:51 Z Kmcode Cultivation (JOI17_cultivation) C++14
65 / 100
 2000 ms 5152 KB 
#include "bits/stdc++.h"
using namespace std;


#define MAX 2002

int n;
int r;
int c;

vector<pair<long long int, long long int> > v;


vector<long long int> vv;

struct st {
	map<long long int, int> mp;
	priority_queue<pair<long long int, long long int> > q;
	long long int las_up;
	long long int las_dw;
	long long int las_md;
	bool changu;
	bool changd;
	bool changm;
	st() {
		changu = changd=changm=true;
		
	}
	void ins(long long int val) {
		mp[val]++;
		changu = changd = changm = true;
		auto it = mp.lower_bound(val);
		if (next(it) != mp.end()) {
			q.push(make_pair((*next(it)).first - (*it).first, (*it).first));
		}
		if (it != mp.begin()) {
			q.push(make_pair(-(*prev(it)).first + (*it).first, (*prev(it)).first));
		}
	}
	void er(long long int val) {
		mp[val]--;
		changu = changd = changm = true;
		if (mp[val] == 0) {
			mp.erase(val);
			auto it = mp.lower_bound(val);
			if (it != mp.begin() && it != mp.end()) {
				q.push(make_pair(-(*prev(it)).first + (*it).first, (*prev(it)).first));
			}
		}
	}
	long long int up() {
		if (changu == false) {
			return las_up;
		}
		changu = false;
		if (mp.size() == 0) {
			las_up = LLONG_MAX / 100LL;
			return LLONG_MAX / 100LL;
		}
		las_up = (*mp.begin()).first;
		return las_up;
	}
	long long int dw() {
		if (changd == false) {
			return las_dw;
		}
		changd = false;
		if (mp.size() == 0) {
			las_dw = LLONG_MAX / 100LL;
			return LLONG_MAX / 100LL;
		}
		las_dw= r - (*mp.rbegin()).first - 1LL;
		return las_dw;
	}
	long long int mid() {
		if (changm == false) {
			return las_md;
		}
		changm = false;
		while (!q.empty()) {
			long long int n1 = q.top().second;
			long long int n2 = q.top().first + n1;
			if (mp.count(n1) == 0 || mp.count(n2) == 0) {
				q.pop();
				continue;
			}
			auto it = mp.upper_bound(n1);
			if ((*it).first != n2) {
				q.pop();
				continue;
			}
			las_md=n2 - n1 - 1LL;
			return las_md;
		}
		las_md = 0;
		return las_md;
	}
};

st z[2002];
vector<long long int> sear;

struct monotonic_queue {
	pair<long long int, int> v[2002];
	int fr;
	int bc;
	monotonic_queue() {
		fr = 0;
		bc = -1;
	}
	void monotonic_queue1() {
		fr = 0;
		bc = -1;
	}
	void add(pair<long long int, int> p) {
		while (bc>=fr&&v[bc].first <= p.first) {
			bc--;
		}
		v[bc + 1] = p;
		bc++;
	}
	long long int gt(long long int ic) {
		while (sear[v[fr].second] >= ic + c) {
			fr++;
		}
		return v[fr].first;
	}
};
vector<long long int> mg(vector<long long int> &a, vector<long long int> &b) {
	vector<long long int> r;
	int aa = 0;
	int bb = 0;
	while (aa < a.size() || bb < b.size()) {
		if (bb<b.size() && r.size() && r.back() == b[bb]) {
			bb++;
			continue;
		}
		if (aa<a.size() && r.size() && r.back() == a[aa]) {
			aa++;
			continue;
		}
		if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
			r.push_back(b[bb]);
			bb++;
			continue;
		}
		r.push_back(a[aa]);
		aa++;
		continue;
	}
	return r;
}
bool cmp(pair<long long int, long long int> a, pair<long long int, long long int> b) {
	return a.second < b.second;
}


vector<int> las;

long long int u1[MAX];
long long int d1[MAX];
long long int md1[MAX];

monotonic_queue u2;
monotonic_queue d2;
monotonic_queue md2;
int main() {
	scanf("%d%d", &r, &c);
	cin >> n;
	long long int mint = LLONG_MAX;
	long long int maxt = 0;
	for (int i = 0; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		v.push_back(make_pair(a, b));
		mint = min(mint, (long long int)b);
		maxt = max(maxt, (long long int)b);
	}
	for (int i = 0; i < v.size(); i++) {
		sear.push_back(v[i].second + c);
		sear.push_back(v[i].second);
		sear.push_back(v[i].second - c);
	}
	sort(sear.begin(), sear.end());
	sear.erase(unique(sear.begin(), sear.end()), sear.end());
	maxt = c - maxt - 1LL;
	long long int lef_least = mint;
	long long int rig_least = maxt;
	maxt += mint;
	vv.push_back(0);
	v.push_back(make_pair(0, c - 1));
	v.push_back(make_pair(0, 0));
	for (int i = 0; i < v.size(); i++) {
		for (int j = 0; j < v.size(); j++) {
			vv.push_back(v[i].second + c - v[j].second - 1);
			vv.push_back(max(0LL, abs(v[j].second - v[i].second) - 1));
		}
	}
	v.pop_back();
	v.pop_back();
	vv.push_back(maxt);
	sort(vv.begin(), vv.end());
	vv.erase(unique(vv.begin(), vv.end()), vv.end());
	long long int ans = LLONG_MAX;
	sort(v.begin(), v.end(), cmp);
	for (int j = 0; j < v.size(); j++) {
		int id1 = lower_bound(sear.begin(), sear.end(), v[j].second) - sear.begin();
		id1--;
		las.push_back(id1);
	}
	for (int i = 0; i < vv.size(); i++) {
		if (vv[i] < maxt)continue;
		for (int j = 0; j < v.size(); j++) {
			for (int k = las[j] + 1;k+1<sear.size()&&sear[k+1]<=v[j].second+vv[i]+1LL; k++) {
				las[j] = k;
				z[k].ins(v[j].first);
			}
		}
		for (int j = 0; j < sear.size(); j++) {
			u1[j] = z[j].up();
			d1[j]= z[j].dw();
			md1[j] = z[j].mid();
		}
		u2.monotonic_queue1();
		d2.monotonic_queue1();
		md2.monotonic_queue1();
		int idx = sear.size() - 1;
		for (int j = sear.size() - 1; j >= 0; j--) {
			u2.add(make_pair(u1[j], j));
			d2.add(make_pair(d1[j], j));
			md2.add(make_pair(md1[j], j));
			while (sear[idx] > sear[j] + c) {
				idx--;
			}
			if (sear[idx]==sear[j]+c) {
				long long int need = u2.gt(sear[j]) + d2.gt(sear[j]) + max(0LL, md2.gt(sear[j]) - u2.gt(sear[j]) - d2.gt(sear[j]));
				ans = min(ans, need + vv[i]);
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}

Compilation message

cultivation.cpp: In function 'std::vector<long long int> mg(std::vector<long long int>&, std::vector<long long int>&)':
cultivation.cpp:133:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (aa < a.size() || bb < b.size()) {
         ~~~^~~~~~~~~~
cultivation.cpp:133:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (aa < a.size() || bb < b.size()) {
                          ~~~^~~~~~~~~~
cultivation.cpp:134:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && r.size() && r.back() == b[bb]) {
       ~~^~~~~~~~~
cultivation.cpp:138:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (aa<a.size() && r.size() && r.back() == a[aa]) {
       ~~^~~~~~~~~
cultivation.cpp:142:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
       ~~^~~~~~~~~
cultivation.cpp:142:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (bb<b.size() && (aa == a.size() || a[aa]>b[bb])) {
                       ~~~^~~~~~~~~~~
cultivation.cpp: In function 'int main()':
cultivation.cpp:181:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
cultivation.cpp:195:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++) {
                  ~~^~~~~~~~~~
cultivation.cpp:196:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                   ~~^~~~~~~~~~
cultivation.cpp:208:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int j = 0; j < v.size(); j++) {
                  ~~^~~~~~~~~~
cultivation.cpp:213:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vv.size(); i++) {
                  ~~^~~~~~~~~~~
cultivation.cpp:215:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < v.size(); j++) {
                   ~~^~~~~~~~~~
cultivation.cpp:216:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int k = las[j] + 1;k+1<sear.size()&&sear[k+1]<=v[j].second+vv[i]+1LL; k++) {
                            ~~~^~~~~~~~~~~~
cultivation.cpp:221:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < sear.size(); j++) {
                   ~~^~~~~~~~~~~~~
cultivation.cpp:189:16: warning: unused variable 'lef_least' [-Wunused-variable]
  long long int lef_least = mint;
                ^~~~~~~~~
cultivation.cpp:190:16: warning: unused variable 'rig_least' [-Wunused-variable]
  long long int rig_least = maxt;
                ^~~~~~~~~
cultivation.cpp:168:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &r, &c);
  ~~~~~^~~~~~~~~~~~~~~~
cultivation.cpp:174:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 2 ms 1044 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 2 ms 1044 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1148 KB Output is correct
18 Correct 3 ms 1244 KB Output is correct
19 Correct 2 ms 1248 KB Output is correct
20 Correct 2 ms 1248 KB Output is correct
21 Correct 3 ms 1312 KB Output is correct
22 Correct 7 ms 1696 KB Output is correct
23 Correct 3 ms 1696 KB Output is correct
24 Correct 11 ms 2480 KB Output is correct
25 Correct 7 ms 2480 KB Output is correct
26 Correct 17 ms 3504 KB Output is correct
27 Correct 18 ms 3632 KB Output is correct
28 Correct 10 ms 3632 KB Output is correct
29 Correct 20 ms 3632 KB Output is correct
30 Correct 17 ms 3632 KB Output is correct
31 Correct 18 ms 3632 KB Output is correct
32 Correct 19 ms 3632 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 2 ms 1044 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1148 KB Output is correct
18 Correct 3 ms 1244 KB Output is correct
19 Correct 2 ms 1248 KB Output is correct
20 Correct 2 ms 1248 KB Output is correct
21 Correct 3 ms 1312 KB Output is correct
22 Correct 7 ms 1696 KB Output is correct
23 Correct 3 ms 1696 KB Output is correct
24 Correct 11 ms 2480 KB Output is correct
25 Correct 7 ms 2480 KB Output is correct
26 Correct 17 ms 3504 KB Output is correct
27 Correct 18 ms 3632 KB Output is correct
28 Correct 10 ms 3632 KB Output is correct
29 Correct 20 ms 3632 KB Output is correct
30 Correct 17 ms 3632 KB Output is correct
31 Correct 18 ms 3632 KB Output is correct
32 Correct 19 ms 3632 KB Output is correct
33 Execution timed out 2053 ms 5152 KB Time limit exceeded
34 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5152 KB Output is correct
2 Correct 4 ms 5152 KB Output is correct
3 Correct 4 ms 5152 KB Output is correct
4 Correct 4 ms 5152 KB Output is correct
5 Correct 4 ms 5152 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 5 ms 5152 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 4 ms 5152 KB Output is correct
10 Correct 4 ms 5152 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 4 ms 5152 KB Output is correct
13 Correct 3 ms 5152 KB Output is correct
14 Correct 4 ms 5152 KB Output is correct
15 Correct 3 ms 5152 KB Output is correct
16 Correct 4 ms 5152 KB Output is correct
17 Correct 4 ms 5152 KB Output is correct
18 Correct 4 ms 5152 KB Output is correct
19 Correct 4 ms 5152 KB Output is correct
20 Correct 4 ms 5152 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5152 KB Output is correct
2 Correct 4 ms 5152 KB Output is correct
3 Correct 4 ms 5152 KB Output is correct
4 Correct 4 ms 5152 KB Output is correct
5 Correct 4 ms 5152 KB Output is correct
6 Correct 3 ms 5152 KB Output is correct
7 Correct 5 ms 5152 KB Output is correct
8 Correct 4 ms 5152 KB Output is correct
9 Correct 4 ms 5152 KB Output is correct
10 Correct 4 ms 5152 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 4 ms 5152 KB Output is correct
13 Correct 3 ms 5152 KB Output is correct
14 Correct 4 ms 5152 KB Output is correct
15 Correct 3 ms 5152 KB Output is correct
16 Correct 4 ms 5152 KB Output is correct
17 Correct 4 ms 5152 KB Output is correct
18 Correct 4 ms 5152 KB Output is correct
19 Correct 4 ms 5152 KB Output is correct
20 Correct 4 ms 5152 KB Output is correct
21 Correct 81 ms 5152 KB Output is correct
22 Correct 123 ms 5152 KB Output is correct
23 Correct 99 ms 5152 KB Output is correct
24 Correct 76 ms 5152 KB Output is correct
25 Correct 110 ms 5152 KB Output is correct
26 Correct 28 ms 5152 KB Output is correct
27 Correct 113 ms 5152 KB Output is correct
28 Correct 113 ms 5152 KB Output is correct
29 Correct 118 ms 5152 KB Output is correct
30 Correct 128 ms 5152 KB Output is correct
31 Correct 125 ms 5152 KB Output is correct
32 Correct 125 ms 5152 KB Output is correct
33 Correct 130 ms 5152 KB Output is correct
34 Correct 113 ms 5152 KB Output is correct
35 Correct 77 ms 5152 KB Output is correct
36 Correct 134 ms 5152 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 752 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 2 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 2 ms 752 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 2 ms 900 KB Output is correct
11 Correct 2 ms 900 KB Output is correct
12 Correct 2 ms 900 KB Output is correct
13 Correct 2 ms 900 KB Output is correct
14 Correct 2 ms 900 KB Output is correct
15 Correct 2 ms 1044 KB Output is correct
16 Correct 2 ms 1048 KB Output is correct
17 Correct 2 ms 1148 KB Output is correct
18 Correct 3 ms 1244 KB Output is correct
19 Correct 2 ms 1248 KB Output is correct
20 Correct 2 ms 1248 KB Output is correct
21 Correct 3 ms 1312 KB Output is correct
22 Correct 7 ms 1696 KB Output is correct
23 Correct 3 ms 1696 KB Output is correct
24 Correct 11 ms 2480 KB Output is correct
25 Correct 7 ms 2480 KB Output is correct
26 Correct 17 ms 3504 KB Output is correct
27 Correct 18 ms 3632 KB Output is correct
28 Correct 10 ms 3632 KB Output is correct
29 Correct 20 ms 3632 KB Output is correct
30 Correct 17 ms 3632 KB Output is correct
31 Correct 18 ms 3632 KB Output is correct
32 Correct 19 ms 3632 KB Output is correct
33 Execution timed out 2053 ms 5152 KB Time limit exceeded
34 Halted 0 ms 0 KB -