結果
| 問題 |
No.855 ヘビの日光浴
|
| コンテスト | |
| ユーザー |
 FF256grhy
|
| 提出日時 | 2020-09-20 15:32:55 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 10,077 bytes |
| コンパイル時間 | 1,915 ms |
| コンパイル使用メモリ | 198,316 KB |
| 最終ジャッジ日時 | 2025-01-14 18:58:24 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In instantiation of ‘T vin() [with T = std::array<int, 3>]’:
main.cpp:58:79: required from ‘auto vin(N, M ...) [with T = std::array<int, 3>; N = int; M = {}]’
main.cpp:255:29: required from here
main.cpp:56:44: error: no match for ‘operator>>’ (operand types are ‘std::basic_istream<char>’ and ‘std::array<int, 3>’)
56 | template<typename T> T vin() { T v; (* IS) >> v; return v; }
| ~~~~~~~^~~~
In file included from /usr/include/c++/13/sstream:40,
from /usr/include/c++/13/complex:45,
from /usr/include/c++/13/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:127,
from main.cpp:1:
/usr/include/c++/13/istream:325:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(void*&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
325 | operator>>(void*& __p)
| ^~~~~~~~
/usr/include/c++/13/istream:325:25: note: no known conversion for argument 1 from ‘std::array<int, 3>’ to ‘void*&’
325 | operator>>(void*& __p)
| ~~~~~~~^~~
/usr/include/c++/13/istream:224:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(long double&) [with _CharT = char; _Traits = std::char_traits<char>; __istream_type = std::basic_istream<char>]’
224 | operator>>(long double& __f)
| ^~~~~~~~
/usr/include/c++/13/istream:224:31: note: no known conversion for argument 1 from ‘std::array<int, 3>’ to ‘long double&’
224 | operator>>(long double& __f)
| ~~~~~~~~~~~~~^~~
/usr/include/c++/13/istream:220:7: note: candidate: ‘std::basic_istream<_CharT, _Traits>::__istream_type& std::basic_istream<_CharT, _Traits>::operator>>(double&) [with _Ch
ソースコード
#include <bits/stdc++.h>
using namespace std;
using LL = long long int;
#define incII(i, l, r) for(LL i = (l) ; i <= (r); i++)
#define incIX(i, l, r) for(LL i = (l) ; i < (r); i++)
#define incXI(i, l, r) for(LL i = (l) + 1; i <= (r); i++)
#define incXX(i, l, r) for(LL i = (l) + 1; i < (r); i++)
#define decII(i, l, r) for(LL i = (r) ; i >= (l); i--)
#define decIX(i, l, r) for(LL i = (r) - 1; i >= (l); i--)
#define decXI(i, l, r) for(LL i = (r) ; i > (l); i--)
#define decXX(i, l, r) for(LL i = (r) - 1; i > (l); i--)
#define inc(i, n) incIX(i, 0, n)
#define dec(i, n) decIX(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define dec1(i, n) decII(i, 1, n)
auto inII = [](auto x, auto l, auto r) { return (l <= x && x <= r); };
auto inIX = [](auto x, auto l, auto r) { return (l <= x && x < r); };
auto inXI = [](auto x, auto l, auto r) { return (l < x && x <= r); };
auto inXX = [](auto x, auto l, auto r) { return (l < x && x < r); };
auto setmin = [](auto & a, auto b) { return (b < a ? a = b, true : false); };
auto setmax = [](auto & a, auto b) { return (b > a ? a = b, true : false); };
auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); };
auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); };
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define MT make_tuple
#define FI first
#define SE second
#define FR front()
#define BA back()
#define ALL(c) c.begin(), c.end()
#define RALL(c) c.rbegin(), c.rend()
#define RV(c) reverse(ALL(c))
#define SC static_cast
#define SI(c) SC<int>(c.size())
#define SL(c) SC<LL >(c.size())
#define RF(e, c) for(auto & e: c)
#define SF(c, ...) for(auto & [__VA_ARGS__]: c)
#define until(e) while(! (e))
#define if_not(e) if(! (e))
#define ef else if
#define UR assert(false)
auto * IS = & cin;
auto * OS = & cout;
array<string, 3> SEQ = { "", " ", "" };
// input
template<typename T> T in() { T a; (* IS) >> a; return a; }
// input: tuple
template<typename U, int I> void tin_([[maybe_unused]] U & t) { }
template<typename U, int I, typename A, typename ... B> void tin_(U & t) { (* IS) >> get<I>(t); tin_<U, I + 1, B ...>(t); }
template<typename ... T> auto tin() { tuple<T ...> t; tin_<tuple<T ...>, 0, T ...>(t); return t; }
// input: array
template<typename T, int N> auto ain() { array<T, N> a; inc(i, N) { (* IS) >> a[i]; } return a; }
// input: multi-dimensional vector
template<typename T> T vin() { T v; (* IS) >> v; return v; }
template<typename T, typename N, typename ... M> auto vin(N n, M ... m) {
vector<decltype(vin<T, M ...>(m ...))> v(n); inc(i, n) { v[i] = vin<T, M ...>(m ...); } return v;
}
// input: multi-column (tuple<vector>)
template<typename U, int I> void colin_([[maybe_unused]] U & t) { }
template<typename U, int I, typename A, typename ... B> void colin_(U & t) {
get<I>(t).PB(in<A>()); colin_<U, I + 1, B ...>(t);
}
template<typename ... T> auto colin(int n) {
tuple<vector<T> ...> t; inc(i, n) { colin_<tuple<vector<T> ...>, 0, T ...>(t); } return t;
}
// output
void out_([[maybe_unused]] string s) { }
template<typename A> void out_([[maybe_unused]] string s, A && a) { (* OS) << a; }
template<typename A, typename ... B> void out_(string s, A && a, B && ... b) { (* OS) << a << s; out_(s, b ...); }
auto outF = [](auto x, auto y, auto z, auto ... a) { (* OS) << x; out_(y, a ...); (* OS) << z << flush; };
auto out = [](auto ... a) { outF("", " " , "\n", a ...); };
auto outS = [](auto ... a) { outF("", " " , " " , a ...); };
auto outL = [](auto ... a) { outF("", "\n", "\n", a ...); };
auto outN = [](auto ... a) { outF("", "" , "" , a ...); };
// output: multi-dimensional vector
template<typename T> ostream & operator<<(ostream & os, vector<T> const & v) {
os << SEQ[0]; inc(i, SI(v)) { os << (i == 0 ? "" : SEQ[1]) << v[i]; } return (os << SEQ[2]);
}
template<typename T> void vout_(T && v) { (* OS) << v; }
template<typename T, typename A, typename ... B> void vout_(T && v, A a, B ... b) {
inc(i, SI(v)) { (* OS) << (i == 0 ? "" : a); vout_(v[i], b ...); }
}
template<typename T, typename A, typename ... B> void vout (T && v, A a, B ... b) { vout_(v, a, b ...); (* OS) << a << flush; }
template<typename T, typename A, typename ... B> void voutN(T && v, A a, B ... b) { vout_(v, a, b ...); (* OS) << flush; }
// ---- ----
#include <algorithm>
#ifdef _MSC_VER
#include <intrin.h>
#endif
namespace atcoder {
namespace internal {
// @param n `0 <= n`
// @return minimum non-negative `x` s.t. `n <= 2**x`
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)(n)) x++;
return x;
}
// @param n `1 <= n`
// @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0`
int bsf(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
} // namespace internal
} // namespace atcoder
#include <cassert>
#include <vector>
namespace atcoder {
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
public:
segtree() : segtree(0) {}
segtree(int n) : segtree(std::vector<S>(n, e())) {}
segtree(const std::vector<S>& v) : _n(int(v.size())) {
log = internal::ceil_pow2(_n);
size = 1 << log;
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
template <bool (*f)(S)> int max_right(int l) {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
using namespace atcoder;
using S = int;
S op(S a, S b) { return max(a, b); }
S e() { return 0; }
// input/output array
template<typename T, size_t N> istream & operator>>(istream & is, array<T, N> & a) { RF(e, a) { is >> e; } return is; }
template<typename T, size_t N> ostream & operator<<(ostream & os, array<T, N> const & a) {
os << SEQ[0]; inc(i, SI(a)) { os << (i == 0 ? "" : SEQ[1]) << a[i]; } return (os << SEQ[2]);
}
#define UQnoS(v) v.erase(unique(ALL(v)), v.end())
#define UQ(v) sort(ALL(v)); UQnoS(v)
#define LB(v, x) (lower_bound(ALL(v), x) - v.begin())
#define UB(v, x) (upper_bound(ALL(v), x) - v.begin())
int main() {
auto [h_, w_, q] = ain<int, 3>();
auto Q = vin<array<int, 3>>(q);
auto info = [&](int x, int y) -> array<int, 5> {
if(x == 0) { return { 0, y, x, h_, w_ }; }
if(y == h_ + 1) { return { 1, x, h_ + 1 - y, w_, h_ }; }
if(x == w_ + 1) { return { 2, h_ + 1 - y, w_ + 1 - x, h_, w_ }; }
if(y == 0) { return { 3, w_ + 1 - x, y, w_, h_ }; }
UR;
};
vector<vector<int>> v(4, { 0 });
v[0].PB(h_ + 1);
v[1].PB(w_ + 1);
v[2].PB(h_ + 1);
v[3].PB(w_ + 1);
SF(Q, x, y, l) {
auto [t, i, j, h, w] = info(x, y);
v[t].PB(i);
}
RF(e, v) { UQ(e); }
using ST = segtree<S, op, e>;
vector<ST> st(4);
inc(k, 4) { st[k] = ST(SI(v[k])); }
SF(Q, x, y, len) {
auto [t0, i, j, h, w] = info(x, y);
assert(inII(i, 0, h) && j == 0);
int t1 = (t0 + 1) % 4;
int t2 = (t0 + 2) % 4;
int t3 = (t0 + 3) % 4;
int ii = h + 1 - i;
int I = LB(v[t0], i);
int II = LB(v[t2], ii);
j = st[t0].get(I);
vector<array<int, 3>> pos;
pos.PB({ w + 1, -1, -1 });
if(h + 1 - v[t2][II] == i) { pos.PB({ w + 1 - st[t2].get(II), t2, II }); }
int R = st[t1].max_right( 0, [&](S a) -> bool { return (a < ii); });
int L = st[t3].min_left(SI(v[t3]), [&](S a) -> bool { return (a < i); }) - 1;
if(R < SI(v[t1])) { assert(st[t1].get(R) >= ii); pos.PB({ v[t1][R], t1, R }); }
if(L >= 0) { assert(st[t3].get(L) >= i); pos.PB({ w + 1 - v[t3][L], t3, L }); }
sort(ALL(pos));
auto [p, t, P] = pos.FR;
if(p <= j + len) {
if(t != -1) { st[t ].set(P, 0); }
if(true) { st[t0].set(I, 0); }
} else {
st[t0].set(I, j + len);
}
}
LL ans = 0;
inc(k, 4) {
inc(i, SI(v[k])) {
ans += st[k].get(i);
}
}
out(ans);
}