#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const int N = (1<<18) +1, inf = 1e18+200;
//int mod = 998244353;
//int mod = 1000000007;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rnd(l, r) uniform_int_distribution <int> (l, r)(rng)
struct segtree{
vector<int> t;
segtree(){
t.resize(N*4);
};
void upd(int ps, int i = 1, int l = 1, int r = N){
if(l == r){
t[i]++;
return;
}
int m = (l+r)>>1;
if(ps <= m)upd(ps, i*2, l, m);
else upd(ps, i*2+1, m+1, r);
t[i] = t[i*2] + t[i*2+1];
};
int get(int tl, int tr, int i = 1, int l = 1, int r = N){
if(l > tr || r < tl)return 0;
if(tl <= l && r <= tr)return t[i];
int m = (l+r)>>1;
return get(tl, tr, i*2, l, m)+get(tl, tr, i*2+1, m+1, r);
};
};
void solve(){
int n, q;
cin >> n >> q;
vector<array<int, 2>> v(n);
for(auto&[i, j]:v)cin >> i >> j;
sort(rall(v));
vector<array<int,3>> que;
for(int i = 0; i < q; i++){
int a, b, c;
cin >> a >> b >> c;
que.pb({a, b, i});
}
sort(rall(que));
auto compr = [&]()->void{
vector<int> vv;
for(auto [i, j]:v)vv.pb(i),vv.pb(j);
for(auto [i, j, k]:que)vv.pb(i), vv.pb(j);
sort(all(vv));
vv.erase(unique(all(vv)), vv.end());
for(auto &[i, j]:v){
i = lower_bound(all(vv), i)-vv.begin();
j = lower_bound(all(vv), j)-vv.begin();
}
for(auto &[i, j, k]:que){
i = lower_bound(all(vv), i)-vv.begin();
j = lower_bound(all(vv), j)-vv.begin();
}
};compr();
//for(auto [i, j]:v)cout << i << ' ' << j << '\n';
//for(auto [i, j, k]:que)cout << i << ' ' << j << ' ' << k << '\n';
vector<int> ans(q);
int it = 0;
segtree t;
for(int i = 0; i < q; i++){
int a = que[i][0], b = que[i][1], id = que[i][2];
while(it < n && v[it][0] >= a){
t.upd(v[it][1]);
it++;
}
ans[id] = t.get(b, N);
}
for(int i:ans)cout << i << ' ';
cout << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int tt = 1;
//cin >> tt;
while(tt--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
17536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
125 ms |
17536 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
