oj.uz

답안 #123692

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123692 2019-07-02T04:16:15 Z 임유진(#3031) Examination (JOI19_examination) C++14
0 / 100
 704 ms 119308 KB 
#include<stdio.h>
#include<algorithm>

using namespace std;

#define MAXN 100005
#define fi first
#define se second

typedef pair<int, int> pii;

struct NOD {
	NOD *lef, *rig;
	int cnt;

	NOD();
} *nil, *xpst[MAXN], *ypst[MAXN];

NOD::NOD(){
	lef = rig = nil;
	cnt = 0;
}

int X[MAXN], Y[MAXN], A[MAXN], B[MAXN], C[MAXN];
pii xs[MAXN], ds[MAXN], ys[MAXN];
int xidx[MAXN], didx[MAXN], yidx[MAXN];
int ans[MAXN];

void mkpst(NOD *bf, NOD *nw, int l, int r, int x) {
	nw -> cnt = bf -> cnt + 1;
	if(l == r) return;
	int m = (l + r) / 2;
	if(x <= m) {
		nw -> lef = new NOD();
		nw -> rig = bf -> rig;
		mkpst(bf -> lef, nw -> lef, l, m, x);
	}
	else {
		nw -> lef = bf -> lef;
		nw -> rig = new NOD();
		mkpst(bf -> rig, nw -> rig, m + 1, r, x);
	}
}

int gpst(NOD *p, int l, int r, int x, int y) {
	if(x <= l && r <=  y) return p -> cnt;
	if(r < x || y < l) return 0;
	int m = (l + r) / 2;
	return gpst(p -> lef, l, m, x, y) + gpst(p -> rig, m + 1, r, x, y);
}

int main() {
	int N, Q;

	scanf("%d%d", &N, &Q);
	for(int i = 1; i <= N; i++) scanf("%d%d", X+i, Y+i);
	for(int i = 0; i < Q; i++) scanf("%d%d%d", A+i, B+i, C+i);

	for(int i = 1; i <= N; i++) {
		xs[i] = make_pair(X[i], i);
		ys[i] = make_pair(Y[i], i);
		ds[i] = make_pair(X[i] + Y[i], i);
	}
	sort(xs + 1, xs + N + 1);
	sort(ys + 1, ys + N + 1);
	sort(ds + 1, ds + N + 1);

	for(int i = 1; i <= N; i++) {
		xidx[xs[i].se] = i;
		didx[ds[i].se] = i;
		yidx[ys[i].se] = i;
	}
	
	nil = new NOD();
	nil -> lef = nil -> rig = nil;
	xpst[0] = nil;
	for(int i = 1; i <= N; i++) {
		xpst[i] = new NOD();
		mkpst(xpst[i-1], xpst[i], 1, N, xidx[ds[i].se]);
	}
	ypst[N + 1] = nil;
	for(int i = N; i > 0; i--) {
		ypst[i] = new NOD();
		mkpst(ypst[i + 1], ypst[i], 1, N, yidx[ds[i].se]);
	}

	for(int i = 0; i < Q; i++) {
		C[i] = max(C[i], A[i] + B[i]);
		int x = lower_bound(xs + 1, xs + N, make_pair(A[i], 0)) - xs;
		int y = lower_bound(ys + 1, ys + N, make_pair(B[i], 0)) - ys;
		int d = lower_bound(ds + 1, ds + N, make_pair(C[i], 0)) - ds;
		int lcnt = x - 1;
		int dcnt = gpst(xpst[d - 1], 1, N, x, N);
		int rcnt = gpst(ypst[d], 1, N, 1, y - 1);
		ans[i] = N - lcnt - dcnt - rcnt;
	}

	for(int i = 0; i < Q; i++) printf("%d\n", ans[i]);
	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:56:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= N; i++) scanf("%d%d", X+i, Y+i);
                              ~~~~~^~~~~~~~~~~~~~~~~~
examination.cpp:57: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%d", A+i, B+i, C+i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 674 ms 119084 KB Output is correct
2 Incorrect 704 ms 119308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 674 ms 119084 KB Output is correct
2 Incorrect 704 ms 119308 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -