This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
int n , q , MAX_S , MAX_T;
vector<int> S(N) , T(N) , X(N) , Y(N) , Z(N) , ans(N);
vector<pair<int , int>> _S , _T;
vector<tuple<int , int , int>> v;
struct node{
node *left , *right;
int sum = 0;
node(int sum = 0) : left(NULL) , right(NULL) , sum(sum) {}
} *t[4 * N];
void UPD(node *&u , int l , int r , int pos , int x){
if(!u){
u = new node();
}
if(l == r){
u->sum += x;
return;
}
int m = (l + r) / 2;
if(pos <= m){
UPD(u->left , l , m , pos , x);
}else{
UPD(u->right , m + 1 , r , pos , x);
}
u->sum = 0;
if(u->left){
u->sum += u->left->sum;
}
if(u->right){
u->sum += u->right->sum;
}
}
int GET(node *&u , int l , int r , int L , int R){
if(l > r || r < L || l > R || u == NULL){
return 0;
}
if(L <= l && r <= R){
return u->sum;
}
int m = (l + r) / 2;
return GET(u->left , l , m , L , R) + GET(u->right , m + 1 , r , L , R);
}
void update(int u , int l , int r , int pos , int t_pos){
if(l == r){
UPD(t[u] , 1 , MAX_T , t_pos , 1);
return;
}
int m = (l + r) / 2;
if(pos <= m){
update(u * 2 , l , m , pos , t_pos);
}else{
update(u * 2 + 1 , m + 1 , r , pos , t_pos);
}
UPD(t[u] , 1 , MAX_T , t_pos , 1);
}
int get(int u , int l , int r , int L , int R , int t_L , int t_R){
if(l > r || r < L || l > R){
return 0;
}
if(L <= l && r <= R){
return GET(t[u] , 1 , MAX_T , t_L , t_R);
}
int m = (l + r) / 2;
return get(u * 2 , l , m , L , R , t_L , t_R) + get(u * 2 + 1 , m + 1 , r , L , R , t_L , t_R);
}
int main(){
cin >> n >> q;
for(int i = 1;i <= n;i ++){
cin >> S[i] >> T[i];
v.push_back({S[i] + T[i] , 1 , i});
_S.push_back({S[i] , i});
_T.push_back({T[i] , i});
}
for(int i = 1;i <= q;i ++){
cin >> X[i] >> Y[i] >> Z[i];
v.push_back({Z[i] , 0 , i});
_S.push_back({X[i] , -i});
_T.push_back({Y[i] , -i});
}
sort(_S.begin() , _S.end());
sort(_T.begin() , _T.end());
for(int i = 0;i < (int)_S.size();i ++){
int lst = (i > 0 ? _S[i - 1].second > 0 ? S[_S[i - 1].second] : X[-_S[i - 1].second] : 1);
if(_S[i].second > 0){
S[_S[i].second] = lst + (i > 0 ? (_S[i].first > _S[i - 1].first) : 0);
}else{
X[-_S[i].second] = lst + (i > 0 ? (_S[i].first > _S[i - 1].first) : 0);
}
}
for(int i = 0;i < (int)_T.size();i ++){
int lst = (i > 0 ? _T[i - 1].second > 0 ? T[_T[i - 1].second] : Y[-_T[i - 1].second] : 1);
if(_T[i].second > 0){
T[_T[i].second] = lst + (i > 0 ? (_T[i].first > _T[i - 1].first) : 0);
}else{
Y[-_T[i].second] = lst + (i > 0 ? (_T[i].first > _T[i - 1].first) : 0);
}
}
MAX_S = max(*max_element(S.begin() , S.end()) , *max_element(X.begin() , X.end()));
MAX_T = max(*max_element(T.begin() , T.end()) , *max_element(Y.begin() , Y.end()));
sort(v.rbegin() , v.rend());
for(auto [value , type , id] : v){
if(type > 0){
update(1 , 1 , MAX_S , S[id] , T[id]);
}else{
ans[id] = get(1 , 1 , MAX_S , X[id] , MAX_S , Y[id] , MAX_T);
}
}
for(int i = 1;i <= q;i ++){
cout << ans[i] << endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |