Submission #258604

---

Source Code Expand

#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <set>
#include <sstream>
#include <numeric>
#include <bitset>
#include <complex>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cctype>
#include <cassert>
using namespace std;

typedef long long ll;
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
bool ISINT(double x){return fabs(x-(int)round(x))<EPS;}
bool ISEQ(double x,double y){return fabs(x-y)<EPS;}
string itos(ll x){stringstream ss;ss<<x;return ss.str();}
#define foreach(itr,c) for(__typeof(c.begin()) itr=c.begin();itr!=c.end();itr++)

typedef pair<int,int> P;

int n;
int t[100002];
P p[100002];

int l[100002], r[100002];
int ans[100002];

int main(void){
  while(cin >> n){
    for(int i = 0; i < n; i++){
      cin >> t[i];
      p[i] = P(t[i], i);

      l[i] = i - 1;
      r[i] = i + 1;
    }

    memset(ans, -1, sizeof(ans));

    sort(p, p + n);

    for(int i = 0; i < n; i++){
      int pos = p[i].second;
      if(ans[pos] != -1) continue;

      int j;
      int lside;
      int pre;

      for(j = pos; 0 <= j; ){
        if(t[j] > p[i].first){
          break;
        }
        pre = j;
        j = l[j];
      }

      lside = j;

      for(j = pre; j < n; ){
        if(t[j] > p[i].first){
          break;
        }
        j = r[j];
      }

      int ansTmp = j - lside - 2;

      for(j = pre; j < n; ){
        if(t[j] > p[i].first){
          break;
        }
        ans[j] = ansTmp;
        j = r[j];
      }

      int lpos = lside;
      int rpos = j;

      if(0 <= lpos) r[lpos] = rpos;
      if(rpos < n)  l[rpos] = lpos;
    }

    for(int i = 0; i < n; i++){
      cout << ans[i] << endl;
    }
  }
}

Submission Info

Judge Result