#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 * 23;
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 (l <= a[i] && b[i] <= r) {
// printf("dodajem store na segm [%d, %d]\n", 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, -1});
} else if (R == M + 1) {
segtree::modify(L, M, {-L, +1});
} else {
if (L == R) return;
int mid = L + R >> 1;
segtree::modify(L, mid, {-L, +1});
segtree::modify(mid + 1, R, {R, -1});
}
}
multiset<int> xs;
int tot_diff = 0;
int tp[N];
void Add(int v) {
for (int i : segs[v]) {
auto it = xs.lower_bound(x[i]);
if (it != xs.end() && *it == x[i]) {
xs.insert(a[i]);
continue;
}
if (xs.empty()) {
addSeg(-1, x[i], +1);
addSeg(x[i], M + 1, +1);
} else if (it == xs.begin()) {
addSeg(-1, *it, -1);
addSeg(-1, x[i], +1);
addSeg(x[i], *it, +1);
} else if (it == xs.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.insert(x[i]);
tp[t[i]]++;
if (tp[t[i]] == 1) tot_diff++;
}
}
void Remove(int v) {
}
void solve(int v, int l, int r) {
if (!v) return;
Add(v);
if (l == r) {
for (int i : QS[v]) ans[i] = (tot_diff == k ? segtree::query(y[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, &q, &k);
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;
}
/*
1 1 1
1000000 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:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
118 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:124:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | scanf("%d%d%d", &n, &q, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:125:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
125 | for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:126:39: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
126 | for (int i = 1; i <= q; i++) scanf("%d%d", &p[i], &y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
324428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
324428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5070 ms |
461176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5056 ms |
453920 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
324428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
147 ms |
324428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
