werid advertisement

```cpp #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct w{ int x, yd, yu, c; bool operator < (const w &g) const { return x < g.x; } }q[60010]; struct tree{ int l, r, cnt, len[11]; }ak[240010]; int s[60010], n, m, k, t; inline int val(int x) { return lower_bound(s + 1, s + m + 1, x) - s; } inline int raw(int x) { return s[x]; } void build(int p, int l, int r) { ak[p].l = l, ak[p].r = r, ak[p].cnt = 0; memset(ak[p].len, 0, sizeof(ak[p].len)); if(l == r) return; int mid = (l + r) >> 1; build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r); } void update(int p, int l, int r) { memset(ak[p].len, 0, sizeof(ak[p].len)); for(int i = 1; i <= ak[p].cnt; i++) ak[p].len[i] = raw(r + 1) - raw(l); for(int i = 1; ak[p].cnt + i <= k; i++) ak[p].len[ak[p].cnt + i] += ak[p * 2].len[i] + ak[p * 2 + 1].len[i]; // printf("%d: (%d %d) cnt: %d len: %d\n", p, l, r, ak[p].cnt, ak[p].len[ak[p].cnt]); } void add(int p, int l, int r, int s, int t, int v) { if(l > t || r < s) return; if(l >= s && r <= t) { ak[p].cnt += v; update(p, l, r); return; } int mid = (l + r) >> 1; add(p * 2, l, mid, s, t, v), add(p * 2 + 1, mid + 1, r, s, t, v); update(p, l, r); } void solve(int step) { int a, b, c, d; long long ans = 0; scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) { scanf("%d%d%d%d", &a, &b, &c, &d); q[2 * i - 1] = (w){a, b, d + 1, 1}, q[2 * i] = (w){c + 1, b, d + 1, -1}; s[2 * i - 1] = b, s[2 * i] = d + 1; } sort(q + 1, q + 2 * n + 1); sort(s + 1, s + 2 * n + 1); m = unique(s + 1, s + 2 * n + 1) - s - 1; build(1, 1, m - 1); for(int i = 1; i <= 2 * n; i++) { // printf("%d (%d,%d), %d----------\n", i, q[i].yd, q[i].yu, q[i].c); if(i > 1 && q[i].x > q[i - 1].x) ans += 1ll * ak[1].len[k] * (q[i].x - q[i - 1].x); add(1, 1, m - 1, val(q[i].yd), val(q[i].yu) - 1, q[i].c); } printf("Case %d: %lld\n", step, ans); } int main() { scanf("%d", &t); for(int i = 1; i <= t; i++) solve(i); return 0; } ```