oj.uz

Submission #123292

# Submission time Handle Problem Language Result Execution time Memory
123292 2019-07-01T05:59:21 Z 임유진(#3021) Two Antennas (JOI19_antennas) C++14
24 / 100
 3000 ms 17244 KB 
#include <stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

#define MAXN 200005
#define fi first
#define se second

typedef pair<int, int> pii;

const int INF = 1e9 + 5;
int H[MAXN], A[MAXN], B[MAXN], L[MAXN], R[MAXN];
int cseg[4*MAXN];
int mnseg[4*MAXN], mxseg[4*MAXN];

void updseg(int idx, int l, int r, int x, int mn, int mx) {
	if(l == r) {
		mnseg[idx] = mn;
		mxseg[idx] = mx;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m) updseg(idx * 2, l, m, x, mn, mx);
	else updseg(idx * 2 + 1, m + 1, r, x, mn, mx);
	mnseg[idx] = min(mnseg[idx * 2], mnseg[idx * 2 + 1]);
	mxseg[idx] = max(mxseg[idx * 2], mxseg[idx * 2 + 1]);
}

int gmax(int idx, int l, int r, int x, int y) {
	//printf("gmax(idx=%d, l=%d, r=%d, x=%d, y=%d)\n", idx, l, r, x, y);
	if(x <= l && r <= y) return mxseg[idx];
	if(r < x || y < l) return -INF;
	int m = (l + r) / 2;
	return max(gmax(idx * 2, l, m, x, y), gmax(idx * 2 + 1, m + 1, r, x, y));
}

int gmin(int idx, int l, int r, int x, int y) {
	if(x <= l && r <= y) return mnseg[idx];
	if(r < x || y < l) return INF;
	int m = (l + r) / 2;
	return min(gmin(idx * 2, l, m, x, y), gmin(idx * 2 + 1, m + 1, r, x, y));
}

int qtime(const pii a) {
	if(a.se == 1) return a.fi + A[a.fi];
	else if(a.se == 2) return a.fi;
	else return a.fi + B[a.fi];
}

bool cmp(const pii a, const pii b) {
	int ta = qtime(a), tb = qtime(b);
	return ta != tb ? ta < tb : a.se < b.se;
}

int maxcost(int l, int m, int r) {
	//printf("maxcost(l = %d, m = %d, r = %d)\n", l, m, r);
	vector<pii> query;
	int ans = -1;

	for(int i = l; i <= m; i++) {
		query.push_back(make_pair(i, 1));
		query.push_back(make_pair(i, 3));
	}
	for(int i = m + 1; i <= r; i++) 
		query.push_back(make_pair(i, 2));
	sort(query.begin(), query.end(), cmp);

	for(int i = 1; i < 4 * (m-l+1); i++) {
		mnseg[i] = INF;
		mxseg[i] = -INF;
	}

	for(auto a : query) {
		//printf("(%d, %d)\n", a.fi, a.se);
		if(a.se == 1) updseg(1, l, m, a.fi, H[a.fi], H[a.fi]);
		else if(a.se== 2) {
			//printf("%d ", ans);
			ans = max(ans, gmax(1, l, m, a.fi - B[a.fi], a.fi - A[a.fi]) - H[a.fi]);
			//printf("%d ", ans);
			ans = max(ans, H[a.fi] - gmin(1, l, m, a.fi - B[a.fi], a.fi - A[a.fi]));
			//printf("%d\n", ans);
		}
		else updseg(1, l, m, a.fi, INF, -INF);
	}
	//printf("maxcost(l=%d, m=%d, r=%d) = %d\n", l, m, r, ans);
	return ans;
}

void mkcseg(int idx, int l, int r) {
	//printf("mkcseg(idx = %d, l = %d, r = %d)\n", idx, l, r);
	if(l == r) {
		cseg[idx] = -1;
		return;
	}
	int m = (l + r) / 2;
	mkcseg(idx * 2, l, m);
	mkcseg(idx * 2 + 1, m + 1, r);
	cseg[idx] = max(max(cseg[idx*2], cseg[idx*2+1]), maxcost(l, m, r));
	//printf("cseg[%d] = %d\n", idx, cseg[idx]);
}

int gcseg(int idx, int l, int r, int x, int y) {
	//printf("gcseg(idx = %d, l = %d, r = %d, x = %d, y = %d)\n", idx, l, r, x, y);
	if(x <= l && r <= y) return cseg[idx];
	int m = (l + r) / 2;
	if(y <= m) return gcseg(idx * 2, l, m, x, y);
	if(x > m) return gcseg(idx * 2 + 1, m + 1, r, x, y);
	return max(max(gcseg(idx * 2, l, m, x, y), gcseg(idx * 2 + 1, m + 1, r, x, y)), maxcost(max(l, x), m, min(r, y)));
}

int main() {
	int N, Q;

	scanf("%d", &N);
	for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
	scanf("%d", &Q);
	for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);

	mkcseg(1, 0, N-1);
	for(int i = 0; i < Q; i++) printf("%d\n", gcseg(1, 0, N-1, L[i]-1, R[i]-1));

	return 0;
}

Compilation message

antennas.cpp: In function 'int main()':
antennas.cpp:116:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:117:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < N; i++) scanf("%d%d%d", H+i, A+i, B+i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:118:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:119:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < Q; i++) scanf("%d%d", L+i, R+i);
                             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 10 ms 380 KB Output is correct
7 Correct 16 ms 396 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 14 ms 376 KB Output is correct
11 Correct 4 ms 404 KB Output is correct
12 Correct 18 ms 376 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 12 ms 416 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 11 ms 376 KB Output is correct
17 Correct 9 ms 380 KB Output is correct
18 Correct 11 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 11 ms 376 KB Output is correct
21 Correct 12 ms 504 KB Output is correct
22 Correct 12 ms 372 KB Output is correct
23 Correct 11 ms 376 KB Output is correct
24 Correct 13 ms 376 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 10 ms 380 KB Output is correct
7 Correct 16 ms 396 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 14 ms 376 KB Output is correct
11 Correct 4 ms 404 KB Output is correct
12 Correct 18 ms 376 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 12 ms 416 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 11 ms 376 KB Output is correct
17 Correct 9 ms 380 KB Output is correct
18 Correct 11 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 11 ms 376 KB Output is correct
21 Correct 12 ms 504 KB Output is correct
22 Correct 12 ms 372 KB Output is correct
23 Correct 11 ms 376 KB Output is correct
24 Correct 13 ms 376 KB Output is correct
25 Execution timed out 3033 ms 3288 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1195 ms 16464 KB Output is correct
2 Correct 1352 ms 17244 KB Output is correct
3 Correct 898 ms 11464 KB Output is correct
4 Correct 1374 ms 17104 KB Output is correct
5 Correct 560 ms 8196 KB Output is correct
6 Correct 1354 ms 17204 KB Output is correct
7 Correct 1140 ms 13376 KB Output is correct
8 Correct 1353 ms 17100 KB Output is correct
9 Correct 163 ms 2596 KB Output is correct
10 Correct 1346 ms 17076 KB Output is correct
11 Correct 785 ms 9824 KB Output is correct
12 Correct 1347 ms 17096 KB Output is correct
13 Correct 942 ms 16972 KB Output is correct
14 Correct 951 ms 16972 KB Output is correct
15 Correct 947 ms 16956 KB Output is correct
16 Correct 907 ms 16952 KB Output is correct
17 Correct 934 ms 17144 KB Output is correct
18 Correct 927 ms 17012 KB Output is correct
19 Correct 938 ms 17120 KB Output is correct
20 Correct 933 ms 16992 KB Output is correct
21 Correct 949 ms 16916 KB Output is correct
22 Correct 949 ms 16972 KB Output is correct
23 Correct 954 ms 17008 KB Output is correct
24 Correct 923 ms 16892 KB Output is correct

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 12 ms 376 KB Output is correct
3 Correct 12 ms 376 KB Output is correct
4 Correct 16 ms 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 10 ms 380 KB Output is correct
7 Correct 16 ms 396 KB Output is correct
8 Correct 17 ms 376 KB Output is correct
9 Correct 7 ms 376 KB Output is correct
10 Correct 14 ms 376 KB Output is correct
11 Correct 4 ms 404 KB Output is correct
12 Correct 18 ms 376 KB Output is correct
13 Correct 8 ms 348 KB Output is correct
14 Correct 12 ms 416 KB Output is correct
15 Correct 8 ms 376 KB Output is correct
16 Correct 11 ms 376 KB Output is correct
17 Correct 9 ms 380 KB Output is correct
18 Correct 11 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 11 ms 376 KB Output is correct
21 Correct 12 ms 504 KB Output is correct
22 Correct 12 ms 372 KB Output is correct
23 Correct 11 ms 376 KB Output is correct
24 Correct 13 ms 376 KB Output is correct
25 Execution timed out 3033 ms 3288 KB Time limit exceeded
26 Halted 0 ms 0 KB -