結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー strangerxxxstrangerxxx
提出日時 2023-12-14 22:15:33
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 74 ms / 5,000 ms
コード長 7,504 bytes
コンパイル時間 5,610 ms
コンパイル使用メモリ 325,192 KB
実行使用メモリ 13,012 KB
最終ジャッジ日時 2023-12-14 22:15:41
合計ジャッジ時間 7,527 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,676 KB
testcase_01 AC 2 ms
6,676 KB
testcase_02 AC 2 ms
6,676 KB
testcase_03 AC 2 ms
6,676 KB
testcase_04 AC 2 ms
6,676 KB
testcase_05 AC 2 ms
6,676 KB
testcase_06 AC 5 ms
6,676 KB
testcase_07 AC 2 ms
6,676 KB
testcase_08 AC 3 ms
6,676 KB
testcase_09 AC 37 ms
8,236 KB
testcase_10 AC 40 ms
6,676 KB
testcase_11 AC 23 ms
6,676 KB
testcase_12 AC 35 ms
8,236 KB
testcase_13 AC 8 ms
6,676 KB
testcase_14 AC 39 ms
13,012 KB
testcase_15 AC 61 ms
13,012 KB
testcase_16 AC 68 ms
13,012 KB
testcase_17 AC 74 ms
13,012 KB
testcase_18 AC 54 ms
13,012 KB
testcase_19 AC 48 ms
12,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma region header
#ifdef STRANGERXXX
#define _GLIBCXX_DEBUG
#endif
/*Pythonで提出してない？*/
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;
// using mint = modint1000000007;
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision;
typedef long long ll;
const ll MOD = 998244353;
typedef unsigned int uint;
typedef unsigned long long ull;
clock_t STARTTIME = clock();
#define TIME() static_cast<double>(clock() - STARTTIME) / CLOCKS_PER_SEC * 1.0
const int INF32 = INT_MAX;
const int IINF32 = INT_MIN;
const uint UINF32 = UINT_MAX;
const long long INF64 = LLONG_MAX;
const long long IINF64 = LLONG_MIN;
const unsigned long long UINF64 = ULLONG_MAX;
const double EPS = 1e-10;
const double PI = 3.141592653589793238;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REP3(i, m, n) for (ll i = (m); i < (ll)(n); i++)
#define REP4(i, m, n, d) for (ll i = (m); i < (ll)(n); i = i + (ll)(d))
#define REPR(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define REP3R(i, m, n) for (ll i = (ll)(n)-1; i >= (ll)(m); i--)
#define REP4R(i, m, n, d) for (ll i = (m); i >= (ll)(n); i = i + (ll)(d))
#define REPA(i, I) for (const auto &i : I)
#define REPB(i, I) for (auto &&i : I)
#define REPIJ(i, j, n)               \
    for (ll i = 0; i < (ll)(n); i++) \
        for (ll j = i + 1; j < (ll)(n); j++)
#define REPIN(a)         \
    for (auto &&i : a) { \
        cin >> i;        \
    }
#define LEN(x) x.size()
typedef pair<ll, ll> PII;
typedef vector<ll> VI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<string> VS;
typedef vector<VS> VVS;
typedef vector<PII> VP;
typedef set<ll> SI;
typedef multiset<ll> MSI;
typedef map<ll, ll> MI;
#include <unordered_set>  // unordered_setがなぜか認識されないので
typedef unordered_set<ll> USI;
typedef unordered_map<ll, ll> UMI;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, VI, greater<ll>> RPQ;
typedef deque<ll> DQ;
#include <random>
random_device seed_gen;
mt19937 mt(seed_gen());
mt19937_64 mt64(seed_gen());
#define RANDINT() mt64()
#define RAND() (double)mt64() / UINF64
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define endl '\n'
#define SUM(V) accumulate((V).begin(), (V).end(), 0LL)
#define ALL(a) (a).begin(), (a).end()
#define SORT(V) sort((V).begin(), (V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
#define REVERSE(V) reverse((V).begin(), (V).end())
#define mod(a, b) ((ll)a % (ll)b + (ll)b) % (ll)b
#define ctoll(c) (ll) c - 48
#define MAXVI(V) *max_element((V).begin(), (V).end())
#define MINVI(V) *min_element((V).begin(), (V).end())
#define UB(V, x) upper_bound((V).begin(), (V).end(), x)
#define LB(V, x) lower_bound((V).begin(), (V).end(), x)
#define bisect_left(V, x) lower_bound((V).begin(), (V).end(), x) - (V).begin()
#define bisect_right(V, x) \
    upper_bound((V).begin(), (V).end(), x + 1) - (V).begin()
#define BS(V, x) binary_search((V).begin(), (V).end(), x)
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define MEMCPY(v, h) memcpy((v), h, sizeof(v))
#define pcnt __builtin_popcount
template <class T>
using V = vector<T>;
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
string join(const vector<string> &v, const char *delim = 0) {
    string s;
    if (!v.empty()) {
        s += v[0];
        for (decltype(v.size()) i = 1, c = v.size(); i < c; ++i) {
            if (delim) s += delim;
            s += v[i];
        }
    }
    return s;
}
void print() { cout << "\n"; }
template <class T, class... A>
void print(const T &first, const A &...rest) {
    if (sizeof...(rest)) {
        cout << first << " ";
        print(rest...);
        return;
    }
    cout << first << "\n";
}
template <class... A>
void print(const A &...rest) {
    print(rest...);
}
#define PRINTD(d) cout << fixed << setprecision(15) << d << "\n"
void PRINTVI(VI V) {
    if (V.size()) {
        cout << V[0];
        REP3(i, 1, V.size()) { cout << " " << V[i]; }
    }
    cout << "\n";
}
void PRINTVVI(VVI V) {
    REPA(v, V) { PRINTVI(v); }
}
void PRINTVS(VS V) { print(join(V, " ")); }
void PRINTVVS(VVS V) {
    REPA(v, V) { PRINTVS(v); }
}
void PRINTPII(PII P) { cout << P.first << " " << P.second << "\n"; }
class range {
   private:
    struct I {
        int x;
        int operator*() { return x; }
        bool operator!=(I &lhs) { return x < lhs.x; }
        void operator++() { ++x; }
    };
    I i, n;

   public:
    range(int n) : i({0}), n({n}) {}
    range(int i, int n) : i({i}), n({n}) {}
    I &begin() { return i; }
    I &end() { return n; }
};
void PRINTMP(MI M) {
    print('{');
    REPA(i, M) { PRINTPII(i); }
    print('}');
}
void PRINTSI(SI S) { PRINTVI(VI(ALL(S))); }
ll pow_ll(ll x, ll y) {
    ll res = 1;
    while (y) {
        if (y & 1) {
            res *= x;
        }
        x *= x;
        y >>= 1;
    }
    return res;
}
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM =
            chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
ll divceil(ll a, ll b) { return (a + (b - 1)) / b; }
PII divmod(ll a, ll b) {
    ll m = mod(a, b);
    return make_pair((a - m) / b, m);
}
uint32_t XORShiftRandom() {
    static uint32_t y = 2463534241;
    y = y ^ (y << 13);
    y = y ^ (y >> 17);
    return y = y ^ (y << 5);
}
#pragma endregion
typedef vector<ll> VI;
struct S {
    ll a;
    ll b;
    ll size;
};
using T = ll;

// 区間取得のときの関数
S op(S a, S b) { return {a.a + b.a, a.b + b.b, a.size + b.size}; }
// opの単位元
S e() { return {0, 0, 0}; }
// ノードxに対し操作fを作用させる関数
S mapping(T f, S x) {
    if (f == 1) {
        return {x.size, 0, x.size};
    } else if (f == 2) {
        return {0, x.size, x.size};
    }
    return {x.a, x.b, x.size};
}
// lazyに対する操作の関数(gにfを作用させる)
T composition(T f, T g) { return (f == 0 ? g : f); }
// mappingの単位元
T id() { return 0; }
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll q;
    cin >> q;
    vector<S> a(n, {0, 0, 1});
    atcoder::lazy_segtree<S, op, e, T, mapping, composition, id> seg(a);
    vector<ll> ans(2, 0);
    REP(_, q) {
        ll x, l, r;
        cin >> x >> l >> r;
        if (x == 0) {
            S p = seg.prod(l, r + 1);
            if (p.a > p.b) {
                ans[0] += p.a;
            } else if (p.a < p.b) {
                ans[1] += p.b;
            }
        } else {
            seg.apply(l, r + 1, x);
        }
        // S ap = seg.all_prod();
        // print(ap.a, ap.b);
    }
    S ap = seg.all_prod();
    ans[0] += ap.a;
    ans[1] += ap.b;
    PRINTVI(ans);
}
0