#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0
#define ll long long
const int N = 100001;
const int A = 200001;
const int INF = (int)1e9;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree <pair <int, int>, null_type, less <pair <int, int> >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
struct query{
int A, B, ind;
};
int n, m, x[N], y[N], z[N];
vector <pair <int, int> > a;
ordered_set v[4 * N];
void insert(ordered_set &s, int v){
auto it = s.upper_bound(make_pair(v, INF));
if(it == s.begin()){
s.insert(make_pair(v, 0));
return;
}
it--;
if(it == s.end() || (*it).first != v) s.insert(make_pair(v, 0));
else s.insert(make_pair(v, (*it).second + 1));
}
void erase(ordered_set &s, int v){
auto it = s.upper_bound(make_pair(v, INF));
assert(it != s.begin());
it--;
assert((*it).first == v);
s.erase(it);
}
void update(int l, int r, int node, int ind, int val){
if(r < l || l > ind || r < ind) return;
insert(v[node], val);
if(l == r) return;
int mid = (l + r) / 2;
if(ind <= mid) update(l, mid, 2 * node, ind, val);
update(mid + 1, r, 2 * node + 1, ind, val);
}
int query(int l, int r, int node, int s, int e, int val){
if(r < l || r < s || l > e) return 0;
if(s <= l && r <= e){
return (int)v[node].size() - v[node].order_of_key(make_pair(val, -INF));
}
int mid = (l + r) / 2;
return query(l, mid, 2 * node, s, e, val) + query(mid + 1, r, 2 * node + 1, s, e, val);
}
void erase(int l, int r, int node, int ind){
if(r < l) return;
erase(v[node], a[ind].second);
if(l == r) return;
int mid = (l + r) / 2;
if(ind <= mid) erase(l, mid, 2 * node, ind);
else erase(mid + 1, r, 2 * node + 1, ind);
}
int query(int suffix, int val){
return query(0, n - 1, 1, suffix, n - 1, val);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
a.resize(n);
for(auto &i : a) cin >> i.first >> i.second;
sort(a.begin(), a.end());
for(int i = 0 ; i < n ; i++){
update(0, n - 1, 1, i, a[i].second);
}
vector <pair <int, pair <int, int> > > all;
for(int i = 0 ; i < n ; i++){
all.push_back(make_pair(a[i].first + a[i].second, make_pair(1, i)));
}
for(int i = 0 ; i < m ; i++){
cin >> x[i] >> y[i] >> z[i];
all.push_back(make_pair(z[i], make_pair(0, i)));
}
vector <int> ans(m);
sort(all.begin(), all.end());
for(auto &i : all){
if(i.second.first == 1) erase(0, n - 1, 1, i.second.second);
else{
int j = i.second.second;
int suff = lower_bound(a.begin(), a.end(), make_pair(x[j], -INF)) - a.begin();
if(suff == n) ans[j] = 0;
else ans[j] = query(suff, y[j]);
}
}
for(auto &i : ans) cout << i << endl;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
38008 KB |
Output is correct |
2 |
Correct |
51 ms |
37880 KB |
Output is correct |
3 |
Correct |
51 ms |
37880 KB |
Output is correct |
4 |
Correct |
51 ms |
37880 KB |
Output is correct |
5 |
Correct |
52 ms |
37932 KB |
Output is correct |
6 |
Correct |
59 ms |
37952 KB |
Output is correct |
7 |
Correct |
91 ms |
40772 KB |
Output is correct |
8 |
Correct |
84 ms |
40696 KB |
Output is correct |
9 |
Correct |
88 ms |
40724 KB |
Output is correct |
10 |
Correct |
89 ms |
40616 KB |
Output is correct |
11 |
Correct |
93 ms |
40696 KB |
Output is correct |
12 |
Correct |
95 ms |
40568 KB |
Output is correct |
13 |
Correct |
113 ms |
40824 KB |
Output is correct |
14 |
Correct |
96 ms |
40740 KB |
Output is correct |
15 |
Correct |
91 ms |
40696 KB |
Output is correct |
16 |
Correct |
75 ms |
40572 KB |
Output is correct |
17 |
Correct |
80 ms |
40696 KB |
Output is correct |
18 |
Correct |
76 ms |
40568 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2938 ms |
154088 KB |
Output is correct |
2 |
Correct |
2902 ms |
153944 KB |
Output is correct |
3 |
Correct |
2853 ms |
153960 KB |
Output is correct |
4 |
Correct |
2342 ms |
154084 KB |
Output is correct |
5 |
Correct |
1552 ms |
154076 KB |
Output is correct |
6 |
Correct |
1546 ms |
154220 KB |
Output is correct |
7 |
Correct |
2914 ms |
154140 KB |
Output is correct |
8 |
Correct |
2785 ms |
154240 KB |
Output is correct |
9 |
Correct |
2495 ms |
154124 KB |
Output is correct |
10 |
Correct |
1162 ms |
154068 KB |
Output is correct |
11 |
Correct |
1738 ms |
153800 KB |
Output is correct |
12 |
Correct |
1275 ms |
153752 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2938 ms |
154088 KB |
Output is correct |
2 |
Correct |
2902 ms |
153944 KB |
Output is correct |
3 |
Correct |
2853 ms |
153960 KB |
Output is correct |
4 |
Correct |
2342 ms |
154084 KB |
Output is correct |
5 |
Correct |
1552 ms |
154076 KB |
Output is correct |
6 |
Correct |
1546 ms |
154220 KB |
Output is correct |
7 |
Correct |
2914 ms |
154140 KB |
Output is correct |
8 |
Correct |
2785 ms |
154240 KB |
Output is correct |
9 |
Correct |
2495 ms |
154124 KB |
Output is correct |
10 |
Correct |
1162 ms |
154068 KB |
Output is correct |
11 |
Correct |
1738 ms |
153800 KB |
Output is correct |
12 |
Correct |
1275 ms |
153752 KB |
Output is correct |
13 |
Correct |
2755 ms |
154084 KB |
Output is correct |
14 |
Correct |
2935 ms |
154088 KB |
Output is correct |
15 |
Correct |
2892 ms |
154176 KB |
Output is correct |
16 |
Correct |
2190 ms |
154028 KB |
Output is correct |
17 |
Correct |
1489 ms |
154200 KB |
Output is correct |
18 |
Correct |
1480 ms |
154116 KB |
Output is correct |
19 |
Correct |
2751 ms |
154292 KB |
Output is correct |
20 |
Correct |
2800 ms |
154208 KB |
Output is correct |
21 |
Correct |
2459 ms |
154248 KB |
Output is correct |
22 |
Correct |
1153 ms |
153956 KB |
Output is correct |
23 |
Correct |
1707 ms |
154004 KB |
Output is correct |
24 |
Correct |
1263 ms |
153808 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
38008 KB |
Output is correct |
2 |
Correct |
51 ms |
37880 KB |
Output is correct |
3 |
Correct |
51 ms |
37880 KB |
Output is correct |
4 |
Correct |
51 ms |
37880 KB |
Output is correct |
5 |
Correct |
52 ms |
37932 KB |
Output is correct |
6 |
Correct |
59 ms |
37952 KB |
Output is correct |
7 |
Correct |
91 ms |
40772 KB |
Output is correct |
8 |
Correct |
84 ms |
40696 KB |
Output is correct |
9 |
Correct |
88 ms |
40724 KB |
Output is correct |
10 |
Correct |
89 ms |
40616 KB |
Output is correct |
11 |
Correct |
93 ms |
40696 KB |
Output is correct |
12 |
Correct |
95 ms |
40568 KB |
Output is correct |
13 |
Correct |
113 ms |
40824 KB |
Output is correct |
14 |
Correct |
96 ms |
40740 KB |
Output is correct |
15 |
Correct |
91 ms |
40696 KB |
Output is correct |
16 |
Correct |
75 ms |
40572 KB |
Output is correct |
17 |
Correct |
80 ms |
40696 KB |
Output is correct |
18 |
Correct |
76 ms |
40568 KB |
Output is correct |
19 |
Correct |
2938 ms |
154088 KB |
Output is correct |
20 |
Correct |
2902 ms |
153944 KB |
Output is correct |
21 |
Correct |
2853 ms |
153960 KB |
Output is correct |
22 |
Correct |
2342 ms |
154084 KB |
Output is correct |
23 |
Correct |
1552 ms |
154076 KB |
Output is correct |
24 |
Correct |
1546 ms |
154220 KB |
Output is correct |
25 |
Correct |
2914 ms |
154140 KB |
Output is correct |
26 |
Correct |
2785 ms |
154240 KB |
Output is correct |
27 |
Correct |
2495 ms |
154124 KB |
Output is correct |
28 |
Correct |
1162 ms |
154068 KB |
Output is correct |
29 |
Correct |
1738 ms |
153800 KB |
Output is correct |
30 |
Correct |
1275 ms |
153752 KB |
Output is correct |
31 |
Correct |
2755 ms |
154084 KB |
Output is correct |
32 |
Correct |
2935 ms |
154088 KB |
Output is correct |
33 |
Correct |
2892 ms |
154176 KB |
Output is correct |
34 |
Correct |
2190 ms |
154028 KB |
Output is correct |
35 |
Correct |
1489 ms |
154200 KB |
Output is correct |
36 |
Correct |
1480 ms |
154116 KB |
Output is correct |
37 |
Correct |
2751 ms |
154292 KB |
Output is correct |
38 |
Correct |
2800 ms |
154208 KB |
Output is correct |
39 |
Correct |
2459 ms |
154248 KB |
Output is correct |
40 |
Correct |
1153 ms |
153956 KB |
Output is correct |
41 |
Correct |
1707 ms |
154004 KB |
Output is correct |
42 |
Correct |
1263 ms |
153808 KB |
Output is correct |
43 |
Correct |
2708 ms |
154124 KB |
Output is correct |
44 |
Correct |
2698 ms |
154124 KB |
Output is correct |
45 |
Correct |
2888 ms |
154384 KB |
Output is correct |
46 |
Correct |
2210 ms |
154208 KB |
Output is correct |
47 |
Correct |
1418 ms |
154192 KB |
Output is correct |
48 |
Correct |
1331 ms |
153828 KB |
Output is correct |
49 |
Correct |
2665 ms |
154240 KB |
Output is correct |
50 |
Correct |
2439 ms |
154296 KB |
Output is correct |
51 |
Correct |
2441 ms |
154212 KB |
Output is correct |
52 |
Correct |
1176 ms |
153960 KB |
Output is correct |
53 |
Correct |
1755 ms |
154000 KB |
Output is correct |