#104769 (C++14) No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ

提出ソース

結果

問題	No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー	Min_25
提出日時	2016-07-18 18:46:32
言語	C++14 (gcc 13.2.0 + boost 1.83.0)
結果	AC
実行時間	44 ms / 5,000 ms
コード長	6,438 bytes
コンパイル時間	1,553 ms
コンパイル使用メモリ	101,192 KB
実行使用メモリ	6,948 KB
最終ジャッジ日時	2024-04-23 16:33:53
合計ジャッジ時間	3,260 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	3 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	3 ms 6,940 KB
testcase_09	AC	20 ms 6,940 KB
testcase_10	AC	18 ms 6,940 KB
testcase_11	AC	12 ms 6,940 KB
testcase_12	AC	20 ms 6,944 KB
testcase_13	AC	5 ms 6,940 KB
testcase_14	AC	16 ms 6,940 KB
testcase_15	AC	30 ms 6,948 KB
testcase_16	AC	33 ms 6,944 KB
testcase_17	AC	44 ms 6,944 KB
testcase_18	AC	24 ms 6,944 KB
testcase_19	AC	25 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#pragma GCC optimize ("O3")
// #pragma GCC target ("avx")
#pragma GCC target ("sse4") // SPOJ, codechef

#include <cstdio>
#include <cassert>
#include <cmath>
#include <cstring>

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <tuple>

#define _rep(_1, _2, _3, _4, name, ...) name
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, c) for (int i = int(a); i < int(b); i += int(c))
#define rep(...) _rep(__VA_ARGS__, rep4, rep3, rep2, _)(__VA_ARGS__)

using namespace std;

using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f80 = long double;

struct SegmentTree {
  struct Node {
    int cnts[2];
    int color;
  };
  using elem = Node;

  SegmentTree(int n) : size_(n) {
    tree = new elem[2 * size_];
  }
  ~SegmentTree() { delete [] tree; }

  void build() {
    rep(i, 2 * size_) tree[i] = {{0, 0}, -1};
  }

  void apply(int k) {
    int ks[30], ki = 0, b = 1;
    for (k >>= 1; k >= 1; k >>= 1, b <<= 1) ks[ki++] = k;

    for (; ki; b >>= 1) {
      int k = ks[--ki];
      if (tree[k].color >= 0) {
        tree[k].cnts[tree[k].color ^ 0] = b;
        tree[k].cnts[tree[k].color ^ 1] = 0;
        tree[2 * k + 0].color = tree[k].color;
        tree[2 * k + 1].color = tree[k].color;
        tree[k].color = -1;
      }
    }
  }

  inline void update_count(int cnts[2], int k, int b) {
    if (tree[k].color >= 0) cnts[tree[k].color] += b;
    else cnts[0] += tree[k].cnts[0], cnts[1] += tree[k].cnts[1];
  }

  inline void fix(int k, int b) {
    assert(tree[k].color == -1);
    int cnts[2] = {};
    update_count(cnts, 2 * k + 0, b >> 1);
    update_count(cnts, 2 * k + 1, b >> 1);
    tree[k].cnts[0] = cnts[0];
    tree[k].cnts[1] = cnts[1];
  }

  void update(int l, int r, int col) {
    bool lup = false, rup = false;
    int b = 1;
    l += size_; r += size_;
    apply(l); apply(r - 1);
    for (; l < r; l >>= 1, r >>= 1, b <<= 1) {
      if (lup) fix(l - 1, b);
      if (rup) fix(r, b);
      if (l & 1) tree[l++].color = col, lup = true;
      if (r & 1) tree[--r].color = col, rup = true;
    }
    for (--l; l < r; l >>= 1, r >>= 1, b <<= 1)  {
      if (lup) fix(l, b);
      if (rup) fix(r, b);
    }
    for (; l; l >>= 1, b <<= 1) fix(l, b);
  }

  pair<int, int> query(int l, int r) {
    l += size_;
    r += size_;
    apply(l); apply(r - 1);
    int cnts[2] = {0, 0};
    for (int b = 1; l < r; l >>= 1, r >>= 1, b <<= 1) {
      if (l & 1) update_count(cnts, l++, b);
      if (r & 1) update_count(cnts, --r, b);
    }
    return {cnts[0], cnts[1]};
  }
  int size_;
  elem* tree;
};

class IO {
  enum { E = 3, N = 1000, SIZE = 1 << 14 };
public:
  IO() : ii(SIZE), oi(0) { init(); }
  ~IO() { if (oi) flush(oi); }
  void init() {
    rep(i, N) {
      int n = i, l = 1;
      rep(j, E) num[i][E - 1 - j] = n % 10 + '0', n /= 10, l += n > 0;
      offsets[i] = E - l;
    }
  }
  char rchar() {
    if (ii == SIZE) { 
      ii = 0;
      int s = fread(in, 1, SIZE, stdin);
      if (s < SIZE) fill(in + s, in + SIZE, EOF);
    }
    return in[ii++];
  }
  int read_int() {
    char c;
    int ret = 0, sign = 0;
    while ((c = rchar()) < '-') {
      if (c == EOF) return -1;
    }
    if (c == '-') sign = 1;
    else ret = c - '0';
    while ((c = rchar()) >= '0') ret = ret * 10 + c - '0';
    return sign ? -ret : ret;
  }
  i64 read_i64() {
    char c;
    i64 ret = 0;
    while ((c = rchar()) < '0');
    ret = c - '0';
    while ((c = rchar()) >= '0') ret = ret * 10 + c - '0';
    return ret;
  }
  u32 read_u32() {
    char c;
    u32 ret = 0;
    while ((c = rchar()) < '0');
    ret = c - '0';
    while ((c = rchar()) >= '0') ret = ret * 10 + c - '0';
    return ret;
  }
  void write_u32(u32 n, bool nl=true) {
    const u32 ten9 = 1e9;
    if (n >= ten9) {
      wchar('0' + n / ten9); n %= ten9;
      u32 q = n / 1000000; n %= 1000000;
      rep(i, 3) wchar(num[q][i]);
      q = n / 1000; n %= 1000;
      rep(i, 3) wchar(num[q][i]); 
      rep(i, 3) wchar(num[n][i]);
    } else if (n >= u32(1e6)) {
      u32 q = n / 1000000; n %= 1000000;
      rep(i, offsets[q], 3) wchar(num[q][i]);
      q = n / 1000; n %= 1000;
      rep(i, 3) wchar(num[q][i]); 
      rep(i, 3) wchar(num[n][i]);
    } else if (n >= u32(1e3)) {
      u32 q = n / 1000; n %= 1000;
      rep(i, offsets[q], 3) wchar(num[q][i]);
      rep(i, 3) wchar(num[n][i]);
    } else {
      rep(i, offsets[n], 3) wchar(num[n][i]);
    }
    if (nl) wchar('\n');
  }
  void write_int(int n, bool nl=true) {
    if (n < 0) {
      n = -n;
      wchar('-');
    }
    write_u32(n, nl);
  }
  void write_u32z(u32 n) {
    u32 q = n / 1000000; n %= 1000000;
    rep(i, 3) wchar(num[q][i]);
    q = n / 1000; n %= 1000;
    rep(i, 3) wchar(num[q][i]);
    rep(i, 3) wchar(num[n][i]);
  }
  void write_u64(u64 n, bool nl=true) {
    static const u64 t18 = u64(1e18);
    static const u32 t9 = u32(1e9);
    if (n >= t18) {
      wchar('0' + n / t18); n %= t18;
      write_u32z(n / t9);
      write_u32z(n % t9);
    } else if (n >= t9) {
      write_u32(n / t9, false);
      write_u32z(n % t9);
    } else {
      write_u32(n, false);
    }
    if (nl) wchar('\n');
  }
  void write_i64(i64 n, bool nl=true) {
    if (n < 0) {
      n = -n;
      wchar('-');
    }
    printf("%lld\n", n);
    write_u64(n, nl);
  }
  void wchar(char c) {
    out[oi++] = c;
    if (oi == SIZE) flush(oi);
  }
  void wstr(const char* str, int len) { rep(i, len) wchar(str[i]); }
  void flush(int size) { fwrite(out, 1, size, stdout); oi = 0; }
  int ii, oi;
  int offsets[N];
  char num[N][E], in[SIZE], out[SIZE];
} io;

void solve() {
  int N;
  while (~(N = io.read_int())) {
    auto tree = SegmentTree(N);
    tree.build();

    int Q = io.read_int();

    i64 a = 0, b = 0;
    rep(i, Q) {
      int c = io.read_int();
      int l = io.read_int();
      int r = io.read_int() + 1;
      if (c >= 1) {
        tree.update(l, r, c - 1);
      } else {
        auto p = tree.query(l, r);
        if (p.first > p.second) a += p.first;
        else if (p.first < p.second) b += p.second;
      }
    }
    auto p = tree.query(0, N);
    a += p.first;
    b += p.second;
    printf("%lld %lld\n", a, b);
  }
}

int main() {
  clock_t beg = clock();
  solve();
  clock_t end = clock();
  fprintf(stderr, "%.3f sec\n", double(end - beg) / CLOCKS_PER_SEC);
  return 0;
}

yukicoder

結果

テストケース

ソースコード