結果
| 問題 | No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ |
| ユーザー |
|
| 提出日時 | 2017-07-23 04:27:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 326 ms / 5,000 ms |
| コード長 | 5,935 bytes |
| コンパイル時間 | 3,175 ms |
| コンパイル使用メモリ | 219,976 KB |
| 最終ジャッジ日時 | 2025-01-05 01:47:56 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
main.cpp: In member function ‘{anonymous}::MaiScanner& {anonymous}::MaiScanner::operator>>(std::string&)’:
main.cpp:63:9: warning: no return statement in function returning non-void [-Wreturn-type]
63 | }
| ^
ソースコード
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include "bits/stdc++.h" // define macro "/D__MAI"
using namespace std;
typedef long long int ll;
#define xprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#define debugv(v) {printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;}
#define debugm(m) {printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}}
#define debuga(m,w) {printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;}
#define debugaa(m,w,h) {printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}}
#define debugaar(m,w,h) {printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}}
#define ALL(v) (v).begin(),(v).end()
#define repeat(cnt,l) for(auto cnt=0;cnt<(l);++cnt)
#define iterate(cnt,b,e) for(auto cnt=(b);cnt!=(e);++cnt)
#define MD 1000000007ll
#define PI 3.1415926535897932384626433832795
template<typename T1, typename T2>
ostream& operator <<(ostream &o, const pair<T1, T2> p) { o << "(" << p.first << ":" << p.second << ")"; return o; }
mt19937 mt(8901016);
inline int rand_int(int l, int h) {
return uniform_int_distribution<>(l, h)(mt);
}
#ifdef __MAI
#define getchar_unlocked getchar
#define putchar_unlocked putchar
#endif
#ifdef __VSCC
#define getchar_unlocked _getchar_nolock
#define putchar_unlocked _putchar_nolock
#endif
namespace {
#define isvisiablechar(c) (0x21<=(c)&&(c)<=0x7E)
class MaiScanner {
public:
template<typename T> void input_integer(T& var) {
var = 0;
T sign = 1;
int cc = getchar_unlocked();
for (; cc<'0' || '9'<cc; cc = getchar_unlocked())
if (cc == '-') sign = -1;
for (; '0' <= cc&&cc <= '9'; cc = getchar_unlocked())
var = (var << 3) + (var << 1) + cc - '0';
var = var*sign;
}
inline int c() { return getchar_unlocked(); }
inline MaiScanner& operator>>(int& var) {
input_integer<int>(var);
return *this;
}
inline MaiScanner& operator>>(long long& var) {
input_integer<long long>(var);
return *this;
}
inline MaiScanner& operator>>(string& var) {
int cc = getchar_unlocked();
for (; !isvisiablechar(cc); cc = getchar_unlocked());
for (; isvisiablechar(cc); cc = getchar_unlocked())
var.push_back(cc);
}
template<typename IT> void in(IT begin, IT end) {
for (auto it = begin; it != end; ++it) *this >> *it;
}
};
}
MaiScanner scanner;
ll square_detail[1010][1010];
ll square[1010];
ll square_1[1010];
ll square_2[1010];
void check_cell_before(int idx) {
if (square[idx] == 2) {
repeat(i, 1000) {
square_detail[idx][i] = 1;
}
square_1[idx] = 1000;
square_2[idx] = 0;
}
else if (square[idx] == 4) {
repeat(i, 1000) {
square_detail[idx][i] = 2;
}
square_1[idx] = 0;
square_2[idx] = 1000;
}
}
void check_cell_after(int idx) {
int ext = 0;
square_1[idx] = 0;
square_2[idx] = 0;
repeat(i, 1000) {
ext |= 1<<square_detail[idx][i];
square_1[idx] += (square_detail[idx][i] == 1);
square_2[idx] += (square_detail[idx][i] == 2);
}
square[idx] = ext;
}
void update_square(int l, int r, int color) {
if (l / 1000 == r / 1000) {
int t = l / 1000;
check_cell_before(t);
iterate(it, l%1000, r % 1000 + 1) {
square_detail[t][it] = color;
}
check_cell_after(t);
return;
}
{
int t = l / 1000;
check_cell_before(t);
iterate(it, l%1000, 1000) {
square_detail[t][it] = color;
}
check_cell_after(t);
}
{
int t = r / 1000;
check_cell_before(t);
iterate(it, 0, r % 1000 + 1) {
square_detail[t][it] = color;
}
check_cell_after(t);
}
{
iterate(it, l / 1000 + 1, r / 1000) {
square[it] = 1 << color;
square_1[it] = (color == 1) * 1000;
square_2[it] = (color == 2) * 1000;
}
}
}
ll bonus_1, bonus_2;
inline void apply_bonus(int color,ll val = 1) {
if (color == 1) bonus_1 += val;
if (color == 2) bonus_2 += val;
}
void attack_chance(int l,int r){
if (l / 1000 == r / 1000) {
int t = l / 1000;
check_cell_before(t);
iterate(it, l % 1000, r % 1000 + 1) {
apply_bonus(square_detail[t][it]);
}
return;
}
{
int t = l / 1000;
check_cell_before(t);
iterate(it, l % 1000, 1000) {
apply_bonus(square_detail[t][it]);
}
}
{
int t = r / 1000;
check_cell_before(t);
iterate(it, 0, r % 1000 + 1) {
apply_bonus(square_detail[t][it]);
}
}
{
iterate(it, l / 1000 + 1, r / 1000) {
bonus_1 += square_1[it];
bonus_2 += square_2[it];
}
}
}
int n;
int main() {
int n_q;
scanner >> n >> n_q;
// ちくしょう！setvalrange関数が無い！
// segtree<int> field(n);
ll total_1 = 0;
ll total_2 = 0;
repeat(qi, n_q) {
int x, l, r;
scanner >> x >> l >> r;
if (x == 0) {
attack_chance(l, r);
if (bonus_1 < bonus_2)
total_2 += bonus_2;
else if (bonus_1 > bonus_2)
total_1 += bonus_1;
bonus_1 = bonus_2 = 0;
}
else {
update_square(l, r, x);
}
}
attack_chance(0, n);
total_1 += bonus_1;
total_2 += bonus_2;
printf("%lld %lld\n", total_1, total_2);
return 0;
}