#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define md ((l+r)>>1)
#define lf (id<<1)
#define rg ((id<<1)|1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> ipii;
const int MAXN = 2e5+10;
const ll INF = 2e18+10;
const ll LOG = 61;
const int MOD = 998244353;
int maxy, maxz;
struct row {
int l, r, mid, val;
row *le, *ri;
void bd(int l2, int r2){
l = l2; r = r2; mid = md;
le = NULL; ri = NULL;
}
void bnc(){
if(le==NULL){
le = new row();
le->bd(l, mid);
}
if(ri==NULL){
ri = new row();
ri->bd(mid+1, r);
}
}
int que(int a, int b){
// cout << l << ' '<< r << ' ' << " que\n";
if(a<=l && r<=b) return val;
if(r<a || b<l) return 0;
bnc();
return le->que(a, b) + ri->que(a, b);
}
int upd(int a, int p){
if(l==r && l==a){
val += p;
// cout << l << ' '<< r << ' ' << val << " upd\n";
return val;
}
if(a<l || r<a) return val;
bnc();
return val = le->upd(a, p) + ri->upd(a, p);
}
};
struct seg {
int l, r, mid;
row *val;
seg *le, *ri;
void bd(int l2, int r2){
l = l2; r = r2; mid = md;
val = new row();
val->bd(1, maxz);
}
void bnc(){
if(le==NULL){
le = new seg();
le->bd(l, mid);
}
if(ri==NULL){
ri = new seg();
ri->bd(mid+1, r);
}
}
int que(int x, int y, int a, int b){
if(x<=l && r<=y) return val->que(a, b);
if(r<x || y<l) return 0;
bnc();
// cout << l << ' '<< r << " queluar\n";
return le->que(x, y, a, b) + ri->que(x, y, a, b);
}
void upd(int x, int a, int p){
if(l==r && l==x){
// cout << l << ' '<< r << " lr_x\n";
val->upd(a, p);
return;
}
if(x<l || r<x) return;
bnc();
// cout << l << ' '<< r << " lr_x\n";
val->upd(a, p); // segtree parentnya juga kena
le->upd(x, a, p); ri->upd(x, a, p);
return;
}
} A;
int n, q;
vector <pii> vec;
vector <pair<pii,pii>> que;
vector <int> cc1, cc2;
int z[MAXN], y[MAXN], X[MAXN], Y[MAXN];
int ans[MAXN];
signed main() {
cin >> n >> q;
for(int i=1; i<=n; i++){
cin >> X[i] >> Y[i];
cc1.pb(Y[i]); cc2.pb(X[i]+Y[i]);
}
for(int i=1; i<=q; i++){
int a, b, c; cin >> a >> b >> c;
que.pb({{a, b}, {c, i}});
// cc1.pb(b); cc2.pb(c);
}
sort(que.rbegin(), que.rend());
cc1.pb(-1);
sort(cc1.begin(), cc1.end());
cc1.resize( unique(cc1.begin(), cc1.end()) - cc1.begin() );
cc2.pb(-1);
sort(cc2.begin(), cc2.end());
cc2.resize( unique(cc2.begin(), cc2.end()) - cc2.begin() );
for(int i=1; i<=n; i++){
y[i] = lower_bound(cc1.begin(), cc1.end(), Y[i]) - cc1.begin();
z[i] = lower_bound(cc2.begin(), cc2.end(), X[i]+Y[i]) - cc2.begin();
vec.pb({X[i], i});
maxy = max(maxy, y[i]);
maxz = max(maxz, z[i]);
// cout << i << ' ' << y[i] << ' ' << z[i] << " ins\n";
}
vec.pb({INF, INF});
sort(vec.rbegin(), vec.rend());
A.bd(1, maxy);
int las = 1;
for(int i=0; i<q; i++){
int a = que[i].fi.fi, id = que[i].se.se;
int b = lower_bound(cc1.begin(), cc1.end(), que[i].fi.se) - cc1.begin();
int c = lower_bound(cc2.begin(), cc2.end(), que[i].se.fi) - cc2.begin();
// cout << id << ' '<< b << ' ' << c << " que\n";
while(las<=n && a <= vec[las].fi){
int idx = vec[las].se;
// cout << y[idx] << ' '<< z[idx] << " idxupd\n";
A.upd(y[idx], z[idx], 1);
las++;
}
ans[id] = A.que(b, maxy, c, maxz);
}
for(int i=1; i<=q; i++) cout << ans[i] << "\n"; //[i==q];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2492 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
39 ms |
30536 KB |
Output is correct |
8 |
Correct |
39 ms |
30808 KB |
Output is correct |
9 |
Correct |
46 ms |
30584 KB |
Output is correct |
10 |
Correct |
13 ms |
6236 KB |
Output is correct |
11 |
Correct |
35 ms |
20564 KB |
Output is correct |
12 |
Correct |
4 ms |
2648 KB |
Output is correct |
13 |
Correct |
30 ms |
23664 KB |
Output is correct |
14 |
Correct |
29 ms |
23792 KB |
Output is correct |
15 |
Correct |
28 ms |
23892 KB |
Output is correct |
16 |
Correct |
17 ms |
12380 KB |
Output is correct |
17 |
Correct |
8 ms |
2908 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3065 ms |
886692 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3065 ms |
886692 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
2 |
Correct |
1 ms |
2392 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
4 |
Correct |
2 ms |
2396 KB |
Output is correct |
5 |
Correct |
1 ms |
2492 KB |
Output is correct |
6 |
Correct |
1 ms |
2396 KB |
Output is correct |
7 |
Correct |
39 ms |
30536 KB |
Output is correct |
8 |
Correct |
39 ms |
30808 KB |
Output is correct |
9 |
Correct |
46 ms |
30584 KB |
Output is correct |
10 |
Correct |
13 ms |
6236 KB |
Output is correct |
11 |
Correct |
35 ms |
20564 KB |
Output is correct |
12 |
Correct |
4 ms |
2648 KB |
Output is correct |
13 |
Correct |
30 ms |
23664 KB |
Output is correct |
14 |
Correct |
29 ms |
23792 KB |
Output is correct |
15 |
Correct |
28 ms |
23892 KB |
Output is correct |
16 |
Correct |
17 ms |
12380 KB |
Output is correct |
17 |
Correct |
8 ms |
2908 KB |
Output is correct |
18 |
Correct |
4 ms |
2652 KB |
Output is correct |
19 |
Execution timed out |
3065 ms |
886692 KB |
Time limit exceeded |
20 |
Halted |
0 ms |
0 KB |
- |