#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e5 + 10;
const int M = 1e8 + 10;
const int K = 5e6 + 10;
const int F = N * 20;
int n, q, k, x[N], t[N], a[N], b[N], p[N], y[N], ls[F], rs[F], root, tsz;
ll ans[N];
vector<int> segs[F], QS[F];
namespace segtree {
pair<ll, int> st[K];
int root, tsz, ls[K], rs[K];
void modify(int& v, int l, int r, int ql, int qr, pair<ll, int> f) {
if (l > r || l > qr || r < ql) return;
if (!v) v = ++tsz;
if (v >= K) while (true) {}
if (ql <= l && r <= qr) {
st[v].first += f.first;
st[v].second += f.second;
return;
}
int mid = l + r >> 1;
modify(ls[v], l, mid, ql, qr, f);
modify(rs[v], mid + 1, r, ql, qr, f);
}
void modify(int l, int r, pair<ll, int> f) { modify(root, 1, M, l, r, f); }
pair<ll, int> query(int v, int l, int r, int p) {
if (!v) return {0LL, 0};
if (l == r) return st[v];
int mid = l + r >> 1;
pair<ll, int> f;
if (p <= mid) f = query(ls[v], l, mid, p);
else f = query(rs[v], mid + 1, r, p);
return {st[v].first + f.first, st[v].second + f.second};
}
ll query(int p) {
pair<ll, int> f = query(root, 1, M, p);
return f.first + p * 1LL * f.second;
}
};
void insStore(int& v, int l, int r, int i) {
if (l > r || l > b[i] || r < a[i]) return;
if (!v) v = ++tsz;
if (a[i] <= l && r <= b[i]) {
// printf("dodajem store[%d] na segm [%d, %d]\n", i, l, r);
segs[v].push_back(i);
return;
}
int mid = l + r >> 1;
insStore(ls[v], l, mid, i);
insStore(rs[v], mid + 1, r, i);
}
void insQuery(int& v, int l, int r, int i) {
if (!v) v = ++tsz;
if (l == r) { QS[v].push_back(i); return; }
int mid = l + r >> 1;
if (y[i] <= mid)
insQuery(ls[v], l, mid, i);
else
insQuery(rs[v], mid + 1, r, i);
}
void addSeg(int L, int R, int d) {
if (L == -1) {
segtree::modify(1, R, {R * d, (-1) * d});
} else if (R == M + 1) {
segtree::modify(L, M, {(-L) * d, (+1) * d});
} else {
if (L == R) return;
int mid = L + R >> 1;
segtree::modify(L, mid, {(-L) * d, (+1) * d});
segtree::modify(mid + 1, R, {(R) * d, (-1) * d});
}
}
multiset<int> xs[N];
int tot_diff = 0, tp[N];
void Add(int v) {
for (int i : segs[v]) {
// printf("dodajem store[%d]\n", i);
auto it = xs[t[i]].lower_bound(x[i]);
if (it != xs[t[i]].end() && *it == x[i]) {
xs[t[i]].insert(x[i]);
tp[t[i]]++;
if (tp[t[i]] == 1) tot_diff++;
continue;
}
if (xs[t[i]].empty()) {
addSeg(-1, x[i], +1);
addSeg(x[i], M + 1, +1);
} else if (it == xs[t[i]].begin()) {
addSeg(-1, *it, -1);
addSeg(-1, x[i], +1);
addSeg(x[i], *it, +1);
} else if (it == xs[t[i]].end()) {
addSeg(*it, M + 1, -1);
addSeg(*prev(it), x[i], +1);
addSeg(x[i], M + 1, +1);
} else {
int L = *prev(it), R = *it;
addSeg(L, R, -1);
addSeg(L, x[i], +1);
addSeg(x[i], R, +1);
}
xs[t[i]].insert(x[i]);
tp[t[i]]++;
if (tp[t[i]] == 1) tot_diff++;
}
}
void Remove(int v) {
for (int i : segs[v]) {
// printf("brisem store[%d]\n", i);
auto it = xs[t[i]].lower_bound(x[i]);
if (xs[t[i]].size() == 1) {
addSeg(-1, x[i], -1);
addSeg(x[i], M + 1, -1);
} else if (it == xs[t[i]].begin()) {
addSeg(-1, x[i], -1);
addSeg(x[i], *next(it), -1);
addSeg(-1, *next(it), +1);
} else if (it == prev(xs[t[i]].end())) {
addSeg(*prev(it), x[i], -1);
addSeg(x[i], M + 1, -1);
addSeg(*prev(it), M + 1, +1);
} else {
addSeg(*prev(it), x[i], -1);
addSeg(x[i], *next(it), -1);
addSeg(*prev(it), *next(it), +1);
}
xs[t[i]].erase(it);
tp[t[i]]--;
if (tp[t[i]] == 0) tot_diff--;
}
}
void solve(int v, int l, int r) {
if (!v) return;
Add(v);
if (l == r) {
for (int i : QS[v]) {
printf("odgovaram na query[%d] tot_diff = %d\n", i, tot_diff);
ans[i] = (tot_diff == k ? segtree::query(p[i]) : -1);
}
Remove(v);
return;
}
int mid = l + r >> 1;
solve(ls[v], l, mid);
solve(rs[v], mid + 1, r);
Remove(v);
}
int main() {
scanf("%d%d%d", &n, &k, &q);
for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
for (int i = 1; i <= q; i++) scanf("%d%d", &p[i], &y[i]);
for (int i = 1; i <= n; i++) insStore(root, 1, M, i);
for (int i = 1; i <= q; i++) insQuery(root, 1, M, i);
solve(root, 1, M);
for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'void segtree::modify(int&, int, int, int, int, std::pair<long long int, int>)':
new_home.cpp:23:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'std::pair<long long int, int> segtree::query(int, int, int, int)':
new_home.cpp:31:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
31 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'void insStore(int&, int, int, int)':
new_home.cpp:50:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'void insQuery(int&, int, int, int)':
new_home.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'void addSeg(int, int, int)':
new_home.cpp:70:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
70 | int mid = L + R >> 1;
| ~~^~~
new_home.cpp: In function 'void solve(int, int, int)':
new_home.cpp:145:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
145 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
151 | scanf("%d%d%d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:152:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:153:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | for (int i = 1; i <= q; i++) scanf("%d%d", &p[i], &y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
296280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
296280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5084 ms |
492224 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5036 ms |
538256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
296280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
132 ms |
296280 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
