fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Data{
  5.   int l, r, bigger, id;
  6. };
  7.  
  8. bool comp(Data a, Data b){
  9. 	cout << "HH";
  10.   return a.bigger > b.bigger;
  11. }
  12.  
  13. int bit[200005], ans[200005];pair<int, int> arr[200005];
  14. int N, Q;
  15. Data ask[200005];
  16.  
  17. void update(int i){
  18.   for(; i <= N; i+=i&-i)
  19.     bit[i]++;
  20. }
  21.  
  22. int getans(int i){
  23.   int res = 0;
  24.   for(; i > 0; i-=i&-i)
  25.     res += bit[i];
  26.   return res;
  27. }
  28.  
  29. int main() {
  30.   cin >> N;
  31.   for(int i = 0; i < N; i++){
  32.     cin >> arr[i].first;
  33.     arr[i].second = i;
  34.   }
  35.   cin >> Q;
  36.   cout << N << " " << Q << "\n";
  37.   for(int i = 0; i < Q; i++){
  38.     cin >> ask[i].l >> ask[i].r >> ask[i].bigger;
  39.     ask[i].l--;
  40.     ask[i].r--;
  41.     ask[i].id = i;
  42.   }
  43.   cout << "success\n";
  44.   sort(arr, arr+N, greater<pair<int, int>>());
  45.   sort(ask, ask+Q, comp);
  46.  
  47.   cout << "success\n";
  48.   int counter = 0;
  49.   for(int i = 0; i < N; i++){
  50.     while(ask[counter].bigger < arr[i].first && counter < Q){
  51.       ans[ask[counter].id] = getans(ask[counter].r + 1) + getans(ask[counter].l);
  52.       counter++;
  53.     }
  54.     update(arr[i].second);
  55.     cout << "success\n";
  56.   }
  57.   for(int i = 0; i < Q; i++){
  58.     cout << ans[i] << "\n";
  59.   }
  60. }
Time limit exceeded #stdin #stdout 5s 21488KB
comments (?)
stdin
copy 
5
5 1 2 3 4
3
2 4 1
4 4 4
1 5 2 
1 5 2
stdout
copy 
5 3
https://ideone.com/SVnsUy
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!