| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 470006 |
2021-09-02T15:02:00 Z |
rainboy |
Plahte (COCI17_plahte) |
C |
|
389 ms |
21764 KB |
#include <stdio.h>
#include <stdlib.h>
#define N 80000
#define M 80000
#define N_ (N + M)
#define K (N * 2 + M)
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int xx[N_ * 2], yy[N_ * 2], n, m, n_, k;
int ta[N], tb[N], cc[M], cc_[M], m_;
int compare_x(int i, int j) {
int ti, tj;
if (xx[i] != xx[j])
return xx[i] - xx[j];
ti = i >= n * 2 ? 0 : ((i & 1) == 0 ? 1 : -1), tj = j >= n * 2 ? 0 : ((j & 1) == 0 ? 1 : -1);
return tj - ti;
}
int compare_c_(int i, int j) {
return cc_[i] != cc_[j] ? cc_[i] - cc_[j] : i - j;
}
int compare_tb(int i, int j) {
return tb[i] - tb[j];
}
int (*compare)(int, int);
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int zz[1 + N * 2], ll[1 + N * 2], rr[1 + N * 2], ii[1 + N * 2], u_, l_, r_;
int node(int i) {
static int _ = 1;
zz[_] = rand_();
ii[_] = i;
return _++;
}
void split(int u, int y) {
if (u == 0) {
u_ = l_ = r_ = 0;
return;
}
if (yy[ii[u]] < y) {
split(rr[u], y);
rr[u] = l_, l_ = u;
} else if (yy[ii[u]] > y) {
split(ll[u], y);
ll[u] = r_, r_ = u;
} else {
u_ = u, l_ = ll[u], r_ = rr[u];
ll[u] = rr[u] = 0;
}
}
int merge(int u, int v) {
if (u == 0)
return v;
if (v == 0)
return u;
if (zz[u] < zz[v]) {
rr[u] = merge(rr[u], v);
return u;
} else {
ll[v] = merge(u, ll[v]);
return v;
}
}
int last(int u) {
return rr[u] == 0 ? u : last(rr[u]);
}
int pp[N_], *ej[N_], eo[N_];
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
void sweep() {
static int hh[K];
int h, h_, i, j;
for (h = 0; h < k; h++)
hh[h] = h;
compare = compare_x, sort(hh, 0, k);
for (i = 0; i < n_; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (h = 0; h < k; h++) {
int p, l, r;
h_ = hh[h];
if (h_ >= n * 2) {
j = h_ - n * 2;
split(u_, yy[h_]);
if (u_)
pp[n + j] = ii[u_] >> 1;
else {
p = l_ == 0 ? -1 : ii[last(l_)];
pp[n + j] = p == -1 ? -1 : ((p & 1) == 0 ? p >> 1 : pp[p >> 1]);
}
u_ = merge(merge(l_, u_), r_);
} else {
i = h_ >> 1;
if ((h_ & 1) == 0) {
split(u_, yy[i << 1 | 0]);
p = l_ == 0 ? -1 : ii[last(l_)];
pp[i] = p == -1 ? -1 : ((p & 1) == 0 ? p >> 1 : pp[p >> 1]);
u_ = merge(merge(l_, merge(node(i << 1 | 0), node(i << 1 | 1))), r_);
} else {
split(u_, yy[i << 1 | 0]), l = l_, split(r_, yy[i << 1 | 1]), r = r_;
u_ = merge(l, r);
}
}
}
for (i = 0; i < n_; i++)
if (pp[i] != -1)
append(pp[i], i);
}
void dfs(int i) {
int o;
if (i >= n)
cc_[m_++] = cc[i - n];
else {
ta[i] = m_;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
}
tb[i] = m_;
}
}
int ft[M];
void update(int i, int n, int x) {
while (i < n) {
ft[i] += x;
i |= i + 1;
}
}
int query(int i) {
int x = 0;
while (i >= 0) {
x += ft[i];
i &= i + 1, i--;
}
return x;
}
void solve() {
static int ii[N], jj[M], prev[M], ans[N];
int i, j;
for (j = 0; j < m; j++)
jj[j] = j;
compare = compare_c_, sort(jj, 0, m);
for (j = 0; j < m; j++)
prev[jj[j]] = j == 0 || cc_[jj[j]] != cc_[jj[j - 1]] ? -1 : jj[j - 1];
for (i = 0; i < n; i++)
ii[i] = i;
compare = compare_tb, sort(ii, 0, n);
for (i = 0, j = 0; i < n; i++) {
int i_ = ii[i];
while (j < tb[i_]) {
update(j, m, 1);
if (prev[j] != -1)
update(prev[j], m, -1);
j++;
}
ans[i_] = query(tb[i_] - 1) - query(ta[i_] - 1);
}
for (i = 0; i < n; i++)
printf("%d\n", ans[i]);
}
int main() {
int i, j;
scanf("%d%d", &n, &m), n_ = n + m, k = n * 2 + m;
for (i = 0; i < n; i++)
scanf("%d%d%d%d", &xx[i << 1 | 0], &yy[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 1]);
for (j = 0; j < m; j++)
scanf("%d%d%d", &xx[n * 2 + j], &yy[n * 2 + j], &cc[j]);
sweep();
for (i = 0; i < n_; i++)
if (pp[i] == -1)
dfs(i);
solve();
return 0;
}
Compilation message
plahte.c: In function 'append':
plahte.c:109:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
109 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
plahte.c: In function 'main':
plahte.c:220:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
220 | scanf("%d%d", &n, &m), n_ = n + m, k = n * 2 + m;
| ^~~~~~~~~~~~~~~~~~~~~
plahte.c:222:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
222 | scanf("%d%d%d%d", &xx[i << 1 | 0], &yy[i << 1 | 0], &xx[i << 1 | 1], &yy[i << 1 | 1]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
plahte.c:224:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
224 | scanf("%d%d%d", &xx[n * 2 + j], &yy[n * 2 + j], &cc[j]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
5956 KB |
Output is correct |
| 2 |
Correct |
81 ms |
7200 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
7456 KB |
Output is correct |
| 2 |
Correct |
116 ms |
8492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
12360 KB |
Output is correct |
| 2 |
Correct |
221 ms |
13788 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
389 ms |
19376 KB |
Output is correct |
| 2 |
Correct |
343 ms |
21268 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
362 ms |
18544 KB |
Output is correct |
| 2 |
Correct |
327 ms |
21764 KB |
Output is correct |
| 3 |
Correct |
1 ms |
332 KB |
Output is correct |
