fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class SegmentTree {
  5. public:
  6.     vector <int> tree;
  7.  
  8.     SegmentTree(int n) {
  9.         tree.resize(4 * n + 1, 0);
  10.     }
  11.  
  12.     // call these methods
  13.     int Query(int n, int i, int j) {
  14.         return Query(1, 0, n - 1, i, j);
  15.     }
  16.  
  17.     void Update(int n, int pos, int val) {
  18.         Update(1, 0, n - 1, pos, val);
  19.     }
  20.  
  21. private:
  22.     void Update(int node, int b, int e, int pos, int val) {
  23.         if (b > e || pos > e || pos < b) {
  24.             return;
  25.         }
  26.  
  27.         if (b == e && b == pos) {
  28.             tree[node] = val;
  29.             return;
  30.         }
  31.  
  32.         int l = node << 1, r = l | 1, m = (b + e) >> 1;
  33.  
  34.         if (pos <= m) {
  35.             Update(l, b, m, pos, val);
  36.         } else {
  37.             Update(r, m + 1, e, pos, val);
  38.         }
  39.  
  40.         tree[node] = tree[l] + tree[r];
  41.     }
  42.  
  43.     int Query(int node, int b, int e, int i, int j) {
  44.         if (b > e || i > e || j < b) {
  45.             return 0;
  46.         }
  47.  
  48.         if (i <= b && j >= e) {
  49.             return tree[node];
  50.         }
  51.  
  52.         int l = node << 1, r = l | 1, m = (b + e) >> 1;
  53.  
  54.         return Query(l, b, m, i, j) + Query(r, m + 1, e, i, j);
  55.     }
  56. };
  57.  
  58. class Solution {
  59. public:
  60.     vector<int> canSeePersonsCount(vector<int>& heights) {
  61.         int n = heights.size();
  62.         stack <int> st;
  63.         // for each i, range[i] = right most index after which ith person can't see
  64.         vector <int> range(n, 0);
  65.         for (int i = n - 1; i >= 0; i--) {
  66.             while (!st.empty() && heights[st.top()] <= heights[i]) st.pop();
  67.             if (st.empty()) {
  68.                 range[i] = n - 1;
  69.             } else {
  70.                 range[i] = st.top();
  71.             }
  72.             st.push(i);
  73.         }
  74.  
  75.         st = stack <int> ();
  76.         vector <int> ans(heights.size(), 0);
  77.  
  78.         SegmentTree *tree = new SegmentTree(heights.size());
  79.         for (int i = 0; i < heights.size(); i++) {
  80.             tree -> Update(n, i, 1);
  81.         }
  82.  
  83.         for (int i = n - 1; i >= 0; i--) {
  84.             ans[i] = tree -> Query(n, i + 1, range[i]);
  85.  
  86.             // eliminate the shorter persons in the range who will be blocked by this person
  87.             while (!st.empty() && heights[st.top()] <= heights[i]) {
  88.                 tree -> Update(n, st.top(), 0);
  89.                 st.pop();
  90.             }
  91.  
  92.             st.push(i);
  93.         }
  94.  
  95.         return ans;
  96.     }
  97. } s;
  98.  
  99. int main() {
  100. 	int t;
  101. 	cin >> t;
  102. 	while (t--) {
  103. 		int n;
  104. 		cin >> n;
  105. 		vector <int> v;
  106. 		for (int i = 1; i <= n; i++) {
  107. 			int val;
  108. 			cin >> val;
  109. 			v.push_back(val);
  110. 		}
  111.  
  112. 		vector <int> ans = s.canSeePersonsCount(v);
  113. 		for (auto val: ans) cout << val << " ";
  114. 		cout << "\n";
  115. 	}
  116. 	return 0;
  117. }
  118.  
  119.  
Success #stdin #stdout 0.01s 5520KB
comments (?)
stdin
copy 
2
6
10 6 8 5 11 9
5
5 1 2 3 10
stdout
copy 
3 1 2 1 1 0 
4 1 1 1 0
https://ideone.com/cC9kmM
language:
C++ (gcc 8.3)
created:
333 days 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!