#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
typedef long long int ll;
typedef pair<int,int> ii;
using namespace __gnu_pbds;
using ordered_set = tree<ii, null_type,less<ii>, rb_tree_tag,tree_order_statistics_node_update>;
const int N = 1e5 + 5;
const int inf = 2e9 + 500;
vector <int> v;
vector <pair<ii,ii>> queries;
map <int,int> id;
int answer,n,q,s[N],t[N],x[N],y[N],z[N],ans[N],tim;
ordered_set seg[N << 2];
void update(int ind,int l,int r,int w,int val) {
if (l > w || r < w)
return;
seg[ind].insert({-val,++tim});
if (l == r)
return;
int mid = (l + r) / 2;
update(ind + ind,l,mid,w,val);
update(ind + ind + 1,mid + 1,r,w,val);
}
void query(int ind,int l,int r,int lw,int rw,int val) {
if (l > rw || r < lw)
return;
if (l >= lw && r <= rw) {
answer += seg[ind].order_of_key({-val,-inf});
return;
}
int mid = (l + r) / 2;
query(ind + ind,l,mid,lw,rw,val);
query(ind + ind + 1,mid + 1,r,lw,rw,val);
}
int query(int x,int val) {
answer = 0;
query(1,1,n + q,x,n + q,val);
return answer;
}
int main() {
cin >> n >> q;
for (int i = 1 ; i <= n ; i++) {
cin >> s[i] >> t[i];
v.push_back(t[i]);
queries.push_back({{s[i],inf},{t[i],s[i] + t[i]}});
}
for (int i = 1 ; i <= q ; i++) {
cin >> x[i] >> y[i] >> z[i];
v.push_back(y[i]);
queries.push_back({{x[i],i},{y[i],z[i]}});
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end()) - v.begin());
int dsa = 0;
for (auto i : v) {
id[i] = ++dsa;
cerr << dsa << ". " << i << endl;
}
sort(queries.begin(),queries.end());
reverse(queries.begin(),queries.end());
for (auto i : queries) {
if (i.first.second == inf) {
cerr << "update -> " << i.second.first << " " << i.second.second << endl;
update(1,1,n + q,id[i.second.first],i.second.second);
}
else {
cerr << "query -> " << i.second.first << " " << i.second.second << endl;
ans[i.first.second] = query(id[i.second.first],i.second.second);
}
}
for (int i = 1 ; i <= q ; i++)
cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
37940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3103 ms |
97256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3103 ms |
97256 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
51 ms |
37940 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
