Submission #1041266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041266		pera	Examination (JOI19_examination)	C++17	100 / 100	1465 ms	662412 KiB

examination

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 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;
   }
}

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57