oj.uz

Submission #123277

# Submission time Handle Problem Language Result Execution time Memory
123277 2019-07-01T05:19:57 Z 임유진(#3021) Two Antennas (JOI19_antennas) C++14
0 / 100
 1323 ms 12628 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 y) {
	if(l == r) {
		mnseg[idx] = mxseg[idx] = y;
		return;
	}
	int m = (l + r) / 2;
	if(x <= m) updseg(idx * 2, l, m, x, y);
	else updseg(idx * 2 + 1, m + 1, r, x, y);
	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));
}

void rmseg(int idx, int l, int r, int x) {
	//printf("rmseg(idx = %d, l = %d, r = %d, x = %d)\n", idx, l, r, x);
	if(l == r) {
		mnseg[idx] = INF;
		mxseg[idx] = -INF;
		return;
	}
	int m = (l + r) / 2;
	if(idx <= m) rmseg(idx * 2, l, m, x);
	else rmseg(idx * 2 + 1, m + 1, r, x);
	mnseg[idx] = min(mnseg[idx * 2], mnseg[idx * 2 + 1]);
	mxseg[idx] = max(mxseg[idx * 2], mxseg[idx * 2 + 1]);
}

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]);
		else if(a.se== 2) {
			if(a.fi - B[a.fi] <= m && a.fi - A[a.fi] >= l) {
				//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 rmseg(1, l, m, a.fi);
	}
	//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:131:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
antennas.cpp:132: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:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &Q);
  ~~~~~^~~~~~~~~~
antennas.cpp:134: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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 12220 KB Output is correct
2 Correct 1262 ms 12628 KB Output is correct
3 Correct 870 ms 8360 KB Output is correct
4 Correct 1323 ms 12540 KB Output is correct
5 Correct 528 ms 6296 KB Output is correct
6 Correct 1280 ms 12552 KB Output is correct
7 Incorrect 1066 ms 9316 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -