CODE FESTIVAL 2014 予選B

Submission #258604

Source codeソースコード

#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

Task問題 D - 登山家
User nameユーザ名 itohjam
Created time投稿日時
Language言語 C++ (G++ 4.6.4)
Status状態 AC
Score得点 100
Source lengthソースコード長 1948 Byte
File nameファイル名
Exec time実行時間 314 ms
Memory usageメモリ使用量 3116 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
Subtask1 30 / 30 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt
Subtask2 70 / 70 sample_01.txt,sample_02.txt,sample_03.txt,subtask1_01.txt,subtask1_02.txt,subtask1_03.txt,subtask1_04.txt,subtask1_05.txt,subtask1_06.txt,subtask1_07.txt,subtask1_08.txt,subtask1_09.txt,subtask1_10.txt,subtask1_11.txt,subtask1_12.txt,subtask1_13.txt,subtask1_14.txt,subtask1_15.txt,subtask1_16.txt,subtask1_17.txt,subtask1_18.txt,subtask1_19.txt,subtask2_01.txt,subtask2_02.txt,subtask2_03.txt,subtask2_04.txt,subtask2_05.txt,subtask2_06.txt,subtask2_07.txt,subtask2_08.txt,subtask2_09.txt,subtask2_10.txt,subtask2_11.txt,subtask2_12.txt,subtask2_13.txt,subtask2_14.txt,subtask2_15.txt,subtask2_16.txt,subtask2_17.txt,subtask2_18.txt,subtask2_19.txt,subtask2_20.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 26 ms 1960 KB
sample_02.txt AC 25 ms 1884 KB
sample_03.txt AC 25 ms 1984 KB
subtask1_01.txt AC 26 ms 1960 KB
subtask1_02.txt AC 25 ms 2076 KB
subtask1_03.txt AC 26 ms 2076 KB
subtask1_04.txt AC 29 ms 2008 KB
subtask1_05.txt AC 28 ms 1904 KB
subtask1_06.txt AC 27 ms 2076 KB
subtask1_07.txt AC 28 ms 1960 KB
subtask1_08.txt AC 33 ms 1904 KB
subtask1_09.txt AC 30 ms 2072 KB
subtask1_10.txt AC 25 ms 2072 KB
subtask1_11.txt AC 29 ms 1956 KB
subtask1_12.txt AC 32 ms 2076 KB
subtask1_13.txt AC 28 ms 1952 KB
subtask1_14.txt AC 27 ms 2076 KB
subtask1_15.txt AC 29 ms 1956 KB
subtask1_16.txt AC 31 ms 1956 KB
subtask1_17.txt AC 32 ms 1956 KB
subtask1_18.txt AC 32 ms 1956 KB
subtask1_19.txt AC 32 ms 1956 KB
subtask2_01.txt AC 159 ms 2596 KB
subtask2_02.txt AC 92 ms 2212 KB
subtask2_03.txt AC 183 ms 2592 KB
subtask2_04.txt AC 188 ms 2588 KB
subtask2_05.txt AC 293 ms 3112 KB
subtask2_06.txt AC 274 ms 3048 KB
subtask2_07.txt AC 279 ms 3116 KB
subtask2_08.txt AC 314 ms 3112 KB
subtask2_09.txt AC 301 ms 3108 KB
subtask2_10.txt AC 279 ms 3096 KB
subtask2_11.txt AC 289 ms 3104 KB
subtask2_12.txt AC 259 ms 3036 KB
subtask2_13.txt AC 282 ms 3112 KB
subtask2_14.txt AC 281 ms 3052 KB
subtask2_15.txt AC 270 ms 3104 KB
subtask2_16.txt AC 275 ms 3060 KB
subtask2_17.txt AC 297 ms 3044 KB
subtask2_18.txt AC 290 ms 3096 KB
subtask2_19.txt AC 282 ms 3108 KB
subtask2_20.txt AC 279 ms 3112 KB