oj.uz

Submission #1041264

# Submission time Handle Problem Language Result Execution time Memory
1041264 2024-08-01T19:52:43 Z pera Examination (JOI19_examination) C++17
0 / 100
 1279 ms 516740 KB 
#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] , 0 , 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] , 1 , 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
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 21 ms 13908 KB Output is correct
8 Correct 21 ms 13904 KB Output is correct
9 Correct 24 ms 14252 KB Output is correct
10 Correct 12 ms 4956 KB Output is correct
11 Correct 11 ms 4732 KB Output is correct
12 Incorrect 7 ms 2908 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 516088 KB Output is correct
2 Correct 1254 ms 516012 KB Output is correct
3 Correct 1279 ms 516740 KB Output is correct
4 Correct 290 ms 54068 KB Output is correct
5 Correct 306 ms 52180 KB Output is correct
6 Incorrect 175 ms 10140 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1245 ms 516088 KB Output is correct
2 Correct 1254 ms 516012 KB Output is correct
3 Correct 1279 ms 516740 KB Output is correct
4 Correct 290 ms 54068 KB Output is correct
5 Correct 306 ms 52180 KB Output is correct
6 Incorrect 175 ms 10140 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 21 ms 13908 KB Output is correct
8 Correct 21 ms 13904 KB Output is correct
9 Correct 24 ms 14252 KB Output is correct
10 Correct 12 ms 4956 KB Output is correct
11 Correct 11 ms 4732 KB Output is correct
12 Incorrect 7 ms 2908 KB Output isn't correct
13 Halted 0 ms 0 KB -