#376941 (C++14) No.877 Range ReLU Query

提出ソース

結果

問題	No.877 Range ReLU Query
ユーザー	lumc_
提出日時	2019-09-07 00:34:09
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	104 ms / 2,000 ms
コード長	6,640 bytes
コンパイル時間	1,467 ms
コンパイル使用メモリ	121,980 KB
実行使用メモリ	9,264 KB
最終ジャッジ日時	2024-04-25 22:07:35
合計ジャッジ時間	3,886 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,940 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,940 KB
testcase_07	AC	2 ms 6,944 KB
testcase_08	AC	3 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	100 ms 8,548 KB
testcase_12	AC	86 ms 8,100 KB
testcase_13	AC	70 ms 7,208 KB
testcase_14	AC	72 ms 7,376 KB
testcase_15	AC	104 ms 9,184 KB
testcase_16	AC	96 ms 8,836 KB
testcase_17	AC	102 ms 8,912 KB
testcase_18	AC	102 ms 9,076 KB
testcase_19	AC	90 ms 9,264 KB
testcase_20	AC	95 ms 9,264 KB

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

ソースコード

raw source code

// includes {{{
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<tuple>
#include<cmath>
#include<random>
#include<cassert>
#include<bitset>
#include<cstdlib>
// #include<deque>
// #include<multiset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;

// SegmentTree( size [, initial] )
// SegmentTree( <data> )
/// --- SegmentTree {{{ ///
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <vector>
template < class Monoid >
struct SegmentTree {
private:
  using T = typename Monoid::T;
  using size_type = std::size_t;
  size_type n;
  std::vector< T > data;
  // call after touch data[i]
  void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }

public:
  SegmentTree() : n(0) {}
  SegmentTree(int n, T initial = Monoid::identity()) : n(n) {
    data.resize(n * 2, initial);
    for(int i = n - 1; i > 0; i--) data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
  }
  template < class InputIter,
           class = typename std::iterator_traits< InputIter >::value_type >
             SegmentTree(InputIter first, InputIter last) : SegmentTree(distance(first, last)) {
               copy(first, last, data.begin() + n);
               // fill from deep
               for(int i = n - 1; i > 0; i--) prop(i);
             }
  SegmentTree(std::vector< T > v) : SegmentTree(v.begin(), v.end()) {}
  SegmentTree(std::initializer_list< T > v) : SegmentTree(v.begin(), v.end()) {}
  void set(size_t i, const T &v) {
    assert(i < n);
    data[i += n] = v;
    while(i >>= 1) prop(i); // propUp
  }
  T get(size_t i) {
    assert(i < n);
    return data[i + n];
  }
  T fold(int l, int r) {
    if(l < 0) l = 0;
    if(l >= r) return Monoid::identity();
    if(r > static_cast< int >(n)) r = n;
    T tmpL = Monoid::identity(), tmpR = Monoid::identity();
    for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);
      if(r & 1) tmpR = Monoid::op(data[--r], tmpR);
    }
    return Monoid::op(tmpL, tmpR);
  }
  size_type size() { return n; }
  inline void dum(int r = -1) {
#ifdef DEBUG
    if(r < 0) r = n;
    DEBUG_OUT << "{";
    for(int i = 0; i < std::min< int >(r, n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);
    DEBUG_OUT << "}" << std::endl;
#endif
  }
};
/// }}}--- ///

/// --- Monoid examples {{{ ///
constexpr long long inf_monoid = 1e18 + 100;
#include <algorithm>
struct Nothing {
  using T = char;
  using Monoid = Nothing;
  using M = T;
  static constexpr T op(const T &, const T &) { return T(); }
  static constexpr T identity() { return T(); }
  template < class X >
    static constexpr X actInto(const M &, long long, const X &x) {
      return x;
    }
};

template < class U = long long >
struct RangeMin {
  using T = U;
  static T op(const T &a, const T &b) { return std::min< T >(a, b); }
  static constexpr T identity() { return T(inf_monoid); }
};

template < class U = long long >
struct RangeMax {
  using T = U;
  static T op(const T &a, const T &b) { return std::max< T >(a, b); }
  static constexpr T identity() { return T(-inf_monoid); }
};

template < class U = long long >
struct RangeSum {
  using T = U;
  static T op(const T &a, const T &b) { return a + b; }
  static constexpr T identity() { return T(0); }
};

template < class U >
struct RangeProd {
  using T = U;
  static T op(const T &a, const T &b) { return a * b; }
  static constexpr T identity() { return T(1); }
};

template < class U = long long >
struct RangeOr {
  using T = U;
  static T op(const T &a, const T &b) { return a | b; }
  static constexpr T identity() { return T(0); }
};

#include <bitset>

template < class U = long long >
struct RangeAnd {
  using T = U;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return T(-1); }
};

template < size_t N >
struct RangeAnd< std::bitset< N > > {
  using T = std::bitset< N >;
  static T op(const T &a, const T &b) { return a & b; }
  static constexpr T identity() { return std::bitset< N >().set(); }
};

/// }}}--- ///

using Seg = SegmentTree< RangeSum<> >;

// .add(i, v)   : bit[i] += v
// .get(i)      : bit[i]
// .sum(i)      : bit[0] + ... + bit[i]
// .range(l, r) : bit[l] + ... + bit[r]
// .lower_bound(T v) : min i that satisfies .sum(i) >= v
//    - use only when bit[i] >= 0 for all i > 0
/// --- Binary Indexed Tree {{{ ///
#include <cassert>
#include <vector>
template < class T = long long >
struct BinaryIndexedTree {
  using size_type = std::size_t;
  size_type n, m;
  T identity;
  std::vector< T > data;
  BinaryIndexedTree() : n(0) {}
  BinaryIndexedTree(int n, T identity = T())
    : n(n), identity(identity), data(n, identity) {
      m = 1;
      while(m < n) m <<= 1;
    }
  void add(size_type i, T x) {
    assert(i < n);
    i++;
    while(i <= n) {
      data[i - 1] = data[i - 1] + x;
      i += i & -i;
    }
  }
  T sum(int i) {
    if(i < 0) return identity;
    if(i >= n) i = n - 1;
    i++;
    T s = identity;
    while(i > 0) {
      s = s + data[i - 1];
      i -= i & -i;
    }
    return s;
  }
  T get(int i) { return sum(i) - sum(i - 1); }
  T range(int a, int b) { return sum(b) - sum(a - 1); }
  size_type lower_bound(T w) {
    size_type i = 0;
    for(size_type k = m; k > 0; k >>= 1) {
      if(i + k <= n && data[i + k - 1] < w) w -= data[(i += k) - 1];
    }
    return i;
  }
};
/// }}}--- ///

template < class T = long long >
using BIT = BinaryIndexedTree< T >;



int n, q;
int l[112345], r[112345], x[112345];
ll ans[112345];

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  cin >> n >> q;

  Seg seg(n);
  BIT<> bit(n);
  
  vector<pair<int, int>> v;
  for(int i = 0; i < n; i++) {
    bit.add(i, 1);
    int a;
    cin >> a;
    seg.set(i, a);
    v.emplace_back(a, i);
  }
  
  sort(begin(v), end(v));
  
  vector<pair<int, int>> w;
  for(int i = 0; i < q; i++) {
    int t;
    cin >> t >> l[i] >> r[i] >> x[i];
    l[i]--;
    w.emplace_back(x[i], i);
  }
  sort(rbegin(w), rend(w));
  
  
  for(int i = 0; i < n; i++) {
    int id = v[i].second;
    while(w.size() and w.back().first < v[i].first) {
      int x, j;
      tie(x, j) = w.back();
      w.pop_back();
      ans[j] = seg.fold(l[j], r[j]) - x * bit.range(l[j], r[j] - 1);
    }
    seg.set(id, 0);
    bit.add(id, -1);
  }
  while(w.size()) {
    int x, j;
    tie(x, j) = w.back();
    w.pop_back();
    ans[j] = seg.fold(l[j], r[j]) - x * bit.range(l[j], r[j] - 1);
  }
  
  for(int i = 0; i < q; i++) cout << ans[i] << "\n";
  
  return 0;
}

yukicoder

結果

テストケース

ソースコード