結果
| 問題 |
No.1000 Point Add and Array Add
|
| コンテスト | |
| ユーザー |
 jell
|
| 提出日時 | 2020-03-07 15:01:22 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 341 ms / 2,000 ms |
| コード長 | 6,533 bytes |
| コンパイル時間 | 946 ms |
| コンパイル使用メモリ | 82,736 KB |
| 最終ジャッジ日時 | 2025-01-09 05:44:04 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 |
コンパイルメッセージ
main.cpp: In member function ‘mono_type mono_type::operator+(const mono_type&) const’:
main.cpp:182:80: warning: no return statement in function returning non-void [-Wreturn-type]
182 | mono_type operator+(const mono_type& rhs) const { mono_type{*this} += rhs; }
| ^
main.cpp: At global scope:
main.cpp:192:1: warning: ISO C++ forbids declaration of ‘main’ with no type [-Wreturn-type]
192 | main()
| ^~~~
ソースコード
#include <iostream>
#include <algorithm>
#include <map>
#include <vector>
#include <string>
#include <cassert>
using namespace std;
void chmin(int &x,int y){x=min(x,y);}
#include <cassert>
#include <vector>
template <class monoid>
class segment_tree
{
using size_type = typename std::vector<monoid>::size_type;
class unique_queue
{
size_type *que, *begin, *end;
bool *in;
public:
unique_queue() : que(), begin(), end(), in() {}
unique_queue(size_type n) : que(new size_type[n]), begin(que), end(que), in(new bool[n]{}) {}
~unique_queue() { delete[] que; delete[] in; }
void clear() { begin = end = que; }
bool empty() const { return begin == end; }
bool push(size_type index)
{
if(in[index]) return false;
return in[*end++ = index] = true;
}
size_type pop() { return in[*begin] = false, *begin++; }
}; // struct unique_queue
size_type size_orig, height, size_ext;
std::vector<monoid> data;
unique_queue que;
void recalc(const size_type node) { data[node] = data[node << 1] + data[node << 1 | 1]; }
void rebuild()
{
while(!que.empty())
{
const size_type index = que.pop() >> 1;
if(index && que.push(index)) recalc(index);
}
que.clear();
}
template <class pred_type>
size_type left_search_subtree(size_type index, const pred_type pred, monoid mono) const
{
assert(index);
while(index < size_ext)
{
const monoid tmp = data[(index <<= 1) | 1] + mono;
if(pred(tmp)) mono = tmp;
else ++index;
}
return ++index -= size_ext;
}
template <class pred_type>
size_type right_search_subtree(size_type index, const pred_type pred, monoid mono) const
{
assert(index);
while(index < size_ext)
{
const monoid tmp = mono + data[index <<= 1];
if(pred(tmp)) ++index, mono = tmp;
}
return (index -= size_ext) < size_orig ? index : size_orig;
}
public:
segment_tree(const size_type n = 0) : size_orig{n}, height(n > 1 ? 32 - __builtin_clz(n - 1) : 0), size_ext{1u << height}, data(size_ext << 1), que(size_ext << 1) {}
segment_tree(const size_type n, const monoid &init) : segment_tree(n)
{
std::fill(std::next(std::begin(data), size_ext), std::end(data), init);
for(size_type i{size_ext}; --i; ) recalc(i);
}
template <class iter_type, class value_type = typename std::iterator_traits<iter_type>::value_type>
segment_tree(iter_type first, iter_type last)
: size_orig(std::distance(first, last)), height(size_orig > 1 ? 32 - __builtin_clz(size_orig - 1) : 0), size_ext{1u << height}, data(size_ext << 1), que(size_ext << 1)
{
static_assert(std::is_constructible<monoid, value_type>::value, "monoid(iter_type::value_type) is not constructible.");
for(auto iter{std::next(std::begin(data), size_ext)}; iter != std::end(data) && first != last; ++iter, ++first) *iter = monoid{*first};
for(size_type i{size_ext}; --i; ) recalc(i);
}
template <class container_type, typename = typename container_type::value_type>
segment_tree(const container_type &cont) : segment_tree(std::begin(cont), std::end(cont)) {}
size_type size() const { return size_orig; }
size_type capacity() const { return size_ext; }
// reference to the element at the index.
typename decltype(data)::reference operator[](size_type index)
{
assert(index < size_orig);
que.push(index |= size_ext);
return data[index];
}
// const reference to the element at the index.
typename decltype(data)::const_reference operator[](size_type index) const
{
assert(index < size_orig);
return data[index |= size_orig];
}
monoid fold(size_type first, size_type last)
{
assert(last <= size_orig);
rebuild();
monoid leftval{}, rightval{};
first += size_ext, last += size_ext;
while(first < last)
{
if(first & 1) leftval = leftval + data[first++];
if(last & 1) rightval = data[--last] + rightval;
first >>= 1, last >>= 1;
}
return leftval + rightval;
}
monoid fold() { return fold(0, size_orig); }
template <class pred_type>
size_type left_search(size_type right, const pred_type pred)
{
assert(right <= size_orig);
rebuild();
right += size_ext;
monoid mono{};
for(size_type left{size_ext}; left != right; left >>= 1, right >>= 1)
{
if((left & 1) != (right & 1))
{
const monoid tmp = data[--right] + mono;
if(!pred(tmp)) return left_search_subtree(right, pred, mono);
mono = tmp;
}
}
return 0;
}
template <class pred_type>
size_type right_search(size_type left, const pred_type pred)
{
assert(left <= size_orig);
rebuild();
left += size_ext;
monoid mono{};
for(size_type right{size_ext << 1}; left != right; left >>= 1, right >>= 1)
{
if((left & 1) != (right & 1))
{
const monoid tmp = mono + data[left];
if(!pred(tmp)) return right_search_subtree(left, pred, mono);
mono = tmp;
++left;
}
}
return size_orig;
}
}; // class segment_tree
struct mono_type
{
int val=0;
mono_type(int v=0) :val(v) {}
// binary operation
mono_type operator+(const mono_type& rhs) const { mono_type{*this} += rhs; }
// operation assignment
mono_type &operator+=(const mono_type &rhs)
{
val+=rhs.val;
return *this;
}
};
main()
{
int n,Q; cin>>n>>Q;
vector<long long> a(n),b(n);
for(auto &e:a) cin>>e;
segment_tree<int> seg(n+1);
while(Q--)
{
char c; int x,y; cin>>c>>x>>y;
if(c=='A')
{
auto k=seg.fold(0,x);
--x;
b[x]+=k*a[x];
a[x]+=y;
seg[x]-=k;
seg[x+1]+=k;
}
else
{
--x;
seg[x]++;
seg[y]--;
}
}
for(int i=0,k=0;i<n;++i)
{
k+=seg[i];
b[i]+=k*a[i];
}
for(auto &e:b)
{
cout << e << " ";
}
cout << "\n";
}