#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int S = 1, E = 1e8 + 1;
struct node
{
ll first, delta;
node *lc, *rc;
node()
{
lc = rc = NULL;
first = delta = 0;
}
void update(int l, int r, int f, int d, int s = S, int e = E)
{
if(r <= s || e <= l) return;
if(l <= s && e <= r)
{
first += f;
delta += d;
return;
}
int mid = (s + e) / 2;
if(l < mid)
{ // this means I have some work on left child
if(lc == NULL) lc = new node();
lc -> update(l, r, f, d, s, mid);
}
if(mid < r)
{
if(rc == NULL) rc = new node();
rc -> update(l, r, f, d, mid, e);
}
}
ll get(int p, int s = S, int e = E)
{
if(p < s || e <= p) return 0;
ll ans = first + (p - s) * delta;
int mid = (s + e) / 2;
if(lc != NULL) ans += lc -> get(p, s, mid);
if(rc != NULL) ans += rc -> get(p, mid, e);
return ans;
}
};
const int Q = 3 * 1e5 + 10, N = Q, T = Q;
node *seg[N];
ll ans[Q], Closed = 0;
map<int, vector<pair<int,int> > > add, rem, qry;
vector<int> events;
multiset<int> st[T];
int n, k, q;
void query(int l, int i)
{
// cerr << "query : " << l << endl;
if(Closed > 0)
{
ans[i] = -1;
return;
}
ans[i] = 0;
for(int j = 1; j <= k; j++)
ans[i] = max(ans[i], seg[j]->get(l));
}
void update(int l, int r, int f, int d, int t) {
seg[t]->update(l, r, f, d);
// cerr << "update" << l << ' ' << r << ' ' << f << ' ' << d << endl;
}
void Add(int x, int t)
{
// cerr << "add " << x << ' ' << t << endl;
if(st[t].empty())
{
Closed--;
st[t].insert(x);
update(x, E, 0, 1, t);
if(S < x)
update(S, x, x - S, -1, t);
return;
}
auto it = st[t].upper_bound(x);
if(it == st[t].end())
{
it--;
update(x, E, 0, 1, t);
}
else
{
int mid = (*it + x + 1) / 2;
update(x, mid, 0, 1, t);
update(mid, *it, *it - mid, -1, t);
if(it != st[t].begin())
{
int e = *it;
it--;
mid = (*it + e) / 2;
update(mid, e, mid - e, 1, t);
}
else
update(S, *it, S - *it, 1, t);
}
it = st[t].upper_bound(x);
if(it == st[t].begin())
{
update(S, x, x - S, -1, t);
}
else
{
it--;
int mid = (x + *it + 1) / 2;
update(*it, mid, 0, 1, t);
update(mid, x, x - mid, -1, t);
int s = *it;
it++;
if(it == st[t].end())
update(s, E, 0, -1, t);
else
{
mid = (s + *it + 1) / 2;
update(s, mid, 0, -1, t);
}
}
st[t].insert(x);
}
void remove(int x, int t)
{
// cerr << "rem " << x << ' ' << t << endl;
st[t].erase(st[t].find(x));
if(st[t].empty())
{
Closed++;
update(x, E, 0, -1, t);
if(S < x)
update(S, x, S - x, +1, t);
return;
}
auto it = st[t].upper_bound(x);
if(it == st[t].end())
{
it--;
update(x, E, 0, -1, t);
}
else
{
int mid = (*it + x + 1) / 2;
update(x, mid, 0, -1, t);
update(mid, *it, mid - *it, +1, t);
if(it != st[t].begin())
{
int e = *it;
it--;
mid = (*it + e) / 2;
update(mid, e, e - mid, -1, t);
}
else
update(S, *it, *it - S, -1, t);
}
it = st[t].upper_bound(x);
if(it == st[t].begin())
{
update(S, x, S - x, +1, t);
}
else
{
it--;
int mid = (x + *it + 1) / 2;
update(*it, mid, 0, -1, t);
update(mid, x, mid - x, +1, t);
int s = *it;
it++;
if(it == st[t].end())
update(s, E, 0, 1, t);
else
{
mid = (s + *it + 1) / 2;
update(s, mid, 0, 1, t);
}
}
}
int main()
{
cin >> n >> k >> q;
Closed = k;
for(int i = 1; i <= k; i ++)
seg[i] = new node();
for(int i = 0; i < n; i ++)
{
int x, t, a, b;
cin >> x >> t >> a >> b;
events.push_back(a);
events.push_back(b);
add[a].push_back({x, t});
rem[b].push_back({x, t});
}
for(int i = 0; i < q; i ++)
{
int l, y;
cin >> l >> y;
events.push_back(y);
qry[y].push_back({l, i});
}
sort(events.begin(), events.end());
events.resize(unique(events.begin(), events.end()) - events.begin());
for(int e : events)
{
// cerr << endl;
// cerr << "Event time : " << e << endl;
if(add.find(e) != add.end())
{
vector<pair<int,int> > &vec = add[e];
for(auto [x, t] : vec)
Add(x, t);
}
if(qry.find(e) != qry.end())
{
vector<pair<int,int> > &vec = qry[e];
for(auto [l, i] : vec)
query(l, i);
}
if(rem.find(e) != rem.end())
{
vector<pair<int,int> > &vec = rem[e];
for(auto [x, t] : vec)
remove(x, t);
}
}
for(int i = 0; i < q; i ++)
cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1476 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1920 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
14428 KB |
Output is correct |
| 2 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 3 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
