#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_updat
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> ost;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
class LazyTree{
//Here ↓
int N; vector<ost> st;
//Here ↓
void upd(int v, int l, int r, int L, int R, int d){
if(r < L or R < l) return;
// add d into sorted array
st[v].insert(d);
if(l == r) return;
int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
upd(v1, l, m, L, R, d);
upd(v2, m+1, r, L, R, d);
return;
}
//↓ Here
int qry(int v, int l, int r, int L, int R, int d){
if(r < L or R < l) return 0;
if(L <= l and r <= R){
int cfvs = st[v].size() - st[v].order_of_key(d);
return cfvs;
}
int m = (l+r)/2, v1 = 2*v, v2 = v1+1;
//Here ↓
return qry(v1, l, m, L, R, d)+qry(v2, m+1, r, L, R, d);
}
public:
LazyTree(int N){st.resize(4*N);this->N = N;}
//Here ↓
void upd(int L, int R, int d){return upd(1, 0, N, L, R, d);}
//↓ Here
int qry(int L, int R, int d){return qry(1, 0, N, L, R, d);}
};
struct node1{
int s, t;
};
struct node2{
int a, b, c, idx;
};
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int n, q; cin >> n >> q;
vector<node1> a(n);
for(auto &i : a) cin >> i.s >> i.t;
sort(all(a), [](auto a, auto b){return a.s+a.t>b.s+b.t;});
vector<node2> cpq(q);
for(int x = 0; x < q; x++){
cin >> cpq[x].a >> cpq[x].b >> cpq[x].c;
cpq[x].idx = x;
}
sort(all(cpq), [](auto z1, auto z2){return z1.c>z2.c;});
set<int> ccrowtmp;
for(int x = 0; x < n; x++){
ccrowtmp.insert(a[x].s);
}
int vcvt = 0;
map<int, int> ccrow;
for(auto v : ccrowtmp){
ccrow[v] = vcvt++;
}
int jp = ccrow.size()+5;
LazyTree ST(jp);
vi sol(q); int stp = 0;
for(auto qq : cpq){
while(stp < n && a[stp].s+a[stp].t >= qq.c){
// insert into merge segtree
int xv = (*ccrow.lower_bound(a[stp].s)).second;
ST.upd(xv, xv, a[stp].t);
stp++;
}
int xv = (*ccrow.lower_bound(qq.a)).second;
sol[qq.idx] = ST.qry(xv, jp, qq.b);
}
for(auto i : sol) cout << i << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2416 ms |
107632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2416 ms |
107632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
