| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 123692 |
2019-07-02T04:16:15 Z |
임유진(#3031) |
Examination (JOI19_examination) |
C++14 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
