AtCoder Regular Contest 080

Submission #1500502

Source codeソースコード

#include <iostream>
#include <vector>
#include <queue>
#define REP(i, a, n) for(int i = ((int) a); i < ((int) n); i++)
#define fi first
#define se second
#define INF 100000000
using namespace std;
typedef pair<int, int> pii;

int N, A[200000];

class SegmentTree {
  int n;
  vector<pii> dat;

public:
  SegmentTree(int size) {
    n = 1;
    while(n < size) n *= 2;
    REP(i, 0, 2 * n - 1) dat.push_back(pii(INF, INF));
  }

  pii query(int a, int b) { return rquery(a, b, 0, 0, n); }

  void update(int k, pii a) {
    k += n - 1;
    dat[k] = a;
    while(k > 0) {
      k = (k - 1) / 2;
      dat[k] = op(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
  }

private:
  pii rquery(int a, int b, int k, int l, int r) {
    if(r <= a || b <= l) return pii(INF, INF);
    if(a <= l && r <= b) return dat[k];
    pii vl = rquery(a, b, k * 2 + 1, l, (l + r) / 2);
    pii vr = rquery(a, b, k * 2 + 2, (l + r) / 2, r);
    return op(vl, vr);
  }

  pii op(pii a, pii b) { return min(a, b); }
};

struct segment {
  int l, r;
  pii v;

public:
  bool operator<(const segment &s) const { return v > s.v; }
};

int main(void) {
  cin >> N;
  REP(i, 0, N) cin >> A[i];

  SegmentTree eve(N / 2), odd(N / 2);
  REP(i, 0, N / 2) {
    eve.update(i, pii(A[i * 2 + 0], i * 2 + 0));
    odd.update(i, pii(A[i * 2 + 1], i * 2 + 1));
  }

  priority_queue<segment> q;
  q.push((segment) { 0, N, eve.query(0, N / 2) });
  vector<int> ans;
  while(q.size()) {
    struct segment s = q.top();
    q.pop();

    if(s.l >= s.r) continue;

    pii t = (s.l % 2 == 0 ? odd : eve).query((s.v.se + 1) / 2, (s.r + 1) / 2);
    ans.push_back(s.v.fi);
    ans.push_back(t.fi);
    q.push((segment) { s.l,        s.v.se, (s.l          % 2 == 0 ? eve : odd).query(s.l / 2,          s.v.se / 2) });
    q.push((segment) { s.v.se + 1, t.se,   ((s.v.se + 1) % 2 == 0 ? eve : odd).query((s.v.se + 1) / 2, t.se / 2) });
    q.push((segment) { t.se + 1,   s.r,    ((t.se + 1)   % 2 == 0 ? eve : odd).query((t.se + 1) / 2,   s.r / 2) });
  }

  REP(i, 0, ans.size()) cout << ans[i] << (i + 1 != N ? " " : "\n");
}

Submission

Task問題 E - Young Maids
User nameユーザ名 ShinyaKato
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 2154 Byte
File nameファイル名
Exec time実行時間 221 ms
Memory usageメモリ使用量 13296 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_00.txt,0_01.txt,0_02.txt
All 800 / 800 0_00.txt,0_01.txt,0_02.txt,1_00.txt,1_01.txt,1_02.txt,1_03.txt,1_04.txt,1_05.txt,1_06.txt,1_07.txt,1_08.txt,1_09.txt,1_10.txt,1_11.txt,1_12.txt,1_13.txt,1_14.txt,1_15.txt,1_16.txt,1_17.txt,1_18.txt,1_19.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 194 ms 12144 KB
1_03.txt AC 191 ms 12912 KB
1_04.txt AC 204 ms 13040 KB
1_05.txt AC 214 ms 13040 KB
1_06.txt AC 213 ms 13040 KB
1_07.txt AC 217 ms 13168 KB
1_08.txt AC 221 ms 12656 KB
1_09.txt AC 187 ms 12400 KB
1_10.txt AC 204 ms 12912 KB
1_11.txt AC 198 ms 11504 KB
1_12.txt AC 209 ms 12656 KB
1_13.txt AC 216 ms 12272 KB
1_14.txt AC 209 ms 12912 KB
1_15.txt AC 213 ms 11888 KB
1_16.txt AC 211 ms 13296 KB
1_17.txt AC 216 ms 12272 KB
1_18.txt AC 213 ms 12656 KB
1_19.txt AC 212 ms 13168 KB