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

• 問題: No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
• ユーザー: mai
• 提出日時: 2017-07-23 04:27:45
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 275 ms / 5,000 ms
• コード長: 5,935 bytes
• コンパイル時間: 3,418 ms
• コンパイル使用メモリ: 219,544 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-09 10:25:50
• 合計ジャッジ時間: 6,076 ms
• ジャッジサーバーID （参考情報）: judge1 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	2 ms; 5,248 KB
testcase_05	AC	3 ms; 5,248 KB
testcase_06	AC	14 ms; 5,248 KB
testcase_07	AC	3 ms; 5,248 KB
testcase_08	AC	5 ms; 5,248 KB
testcase_09	AC	102 ms; 5,248 KB
testcase_10	AC	87 ms; 5,248 KB
testcase_11	AC	76 ms; 5,248 KB
testcase_12	AC	102 ms; 5,248 KB
testcase_13	AC	22 ms; 5,248 KB
testcase_14	AC	194 ms; 5,248 KB
testcase_15	AC	275 ms; 5,248 KB
testcase_16	AC	274 ms; 5,248 KB
testcase_17	AC	212 ms; 5,248 KB
testcase_18	AC	257 ms; 5,248 KB
testcase_19	AC	159 ms; 5,248 KB

コンパイルメッセージ

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;
}