#902545 (C++17) No.2421 entersys?

提出ソース
結果

問題	No.2421 entersys?
ユーザー	T101010101
提出日時	2023-08-12 14:27:03
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	18,976 bytes
コンパイル時間	6,665 ms
コンパイル使用メモリ	336,548 KB
実行使用メモリ	576,280 KB
最終ジャッジ日時	2024-11-19 19:34:16
合計ジャッジ時間	29,278 ms
ジャッジサーバーID （参考情報）	judge1 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	12 ms 14,208 KB
testcase_01	AC	16 ms 16,000 KB
testcase_02	AC	21 ms 19,456 KB
testcase_03	AC	13 ms 15,104 KB
testcase_04	AC	15 ms 16,256 KB
testcase_05	AC	18 ms 17,664 KB
testcase_06	AC	18 ms 17,664 KB
testcase_07	AC	18 ms 17,664 KB
testcase_08	AC	20 ms 18,688 KB
testcase_09	AC	23 ms 21,120 KB
testcase_10	AC	17 ms 17,152 KB
testcase_11	AC	1,132 ms 454,880 KB
testcase_12	AC	1,145 ms 454,656 KB
testcase_13	AC	1,162 ms 455,404 KB
testcase_14	AC	1,194 ms 454,912 KB
testcase_15	AC	1,165 ms 455,296 KB
testcase_16	AC	1,143 ms 457,024 KB
testcase_17	AC	1,149 ms 457,068 KB
testcase_18	AC	1,163 ms 456,876 KB
testcase_19	AC	1,166 ms 456,024 KB
testcase_20	AC	1,180 ms 456,744 KB
testcase_21	AC	892 ms 327,856 KB
testcase_22	AC	1,008 ms 459,668 KB
testcase_23	MLE	-
testcase_24	MLE	-
testcase_25	MLE	-
testcase_26	AC	802 ms 313,728 KB
testcase_27	AC	730 ms 313,600 KB
testcase_28	AC	745 ms 313,984 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#pragma region Macros

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")

#include <bits/extc++.h>
#include <atcoder/all>
using namespace atcoder;
using namespace std;
using namespace __gnu_pbds;

// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// namespace mp = boost::multiprecision;
// using Bint = mp::cpp_int;
// using Bdouble = mp::number<mp::cpp_dec_float<256>>;

#define pb emplace_back
#define int ll
#define endl '\n'
#define sqrt __builtin_sqrtl

using ll = long long;
using ld = long double;
const ld PI = acosl(-1);
const int INF = 1 << 30;
const ll INFL = 1LL << 61;
const int MOD = 998244353;
// const int MOD = 1000000007;

const ld EPS = 1e-10;
const bool equals(ld a, ld b) { return fabs((a) - (b)) < EPS; }

const vector<int> dx = {0, 1, 0, -1, 1, 1, -1, -1}; // → ↓ ← ↑ ↘ ↙ ↖ ↗
const vector<int> dy = {1, 0, -1, 0, 1, -1, -1, 1};

struct Edge {
    int from, to;
    ll cost;
    Edge(int to, ll cost) : from(-1), to(to), cost(cost) {}
    Edge(int from, int to, ll cost) : from(from), to(to), cost(cost) {}
};

__attribute__((constructor))
void constructor() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(12);
}

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        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);
    }
};

int POW(int x, int n) {
    __int128_t ret = 1;
    // if (ret >= INFL) return INFL;
    if (n < 0) { cout << "error" << endl; return 0; }
    else if (x == 1 or n == 0) ret = 1;
    else if (x == -1 && n % 2 == 0) ret = 1; 
    else if (x == -1) ret = -1; 
    else if (n % 2 == 0) ret = POW(x * x, n / 2); // TODO:オーバーフロー対策
    else ret = x * POW(x, n - 1);

    if (ret > 8e18) ret = 0;
    return ret;
}
int floor(int x, int y) { return (x > 0 ? x / y : (x - y + 1) / y); }
int ceil(int x, int y) { return (x > 0 ? (x + y - 1) / y : x / y); }
ll per(int x, int y) {
    if (y == 0) {
        cout << "error" << endl;
        return INFL;
    }
    if (x >= 0 && y > 0) return x / y;
    if (x >= 0 && y < 0) return x / y - (x % y < 0);
    if (x < 0 && y < 0) return x / y + (x % y < 0);
    // if (x < 0 && y > 0) 
    return x / y - (x % y < 0);
}
ll mod(int x, int y) {
    if (y == 0) {
        cout << "error" << endl;
        return INFL;
    }
    if (x >= 0 && y > 0) return x % y;
    if (x >= 0 && y < 0) return x % y;
    if (x < 0 && y < 0) {
        __int128_t ret = x % y;
        ret += (__int128_t)abs(y) * INFL;
        ret %= abs(y);
        return ret;
    }
    // if (x < 0 && y > 0) {
        __int128_t ret = x % y;
        ret += (__int128_t)abs(y) * INFL;
        ret %= abs(y);
        return ret;
    // }
}
int modf(ld x) {
    if (equals(x, 0)) return 0;
	else if (x < 0) return ceill(x);
	else return floorl(x);
}

template <class T> bool chmax(T &a, const T& b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <class T> bool chmin(T &a, const T& b) {
    if (a > b) { a = b; return true; }
    return false;
}

int countl_zero(int N) { return __builtin_clzll(N); }
int countl_one(int N) {
    int ret = 0; while (N % 2) { N /= 2; ret++; }
    return ret;
}
int countr_zero(int N) { return __builtin_ctzll(N); }
int countr_one(int N) {
    int ret = 0, k = 63 - __builtin_clzll(N);
    while (k != -1 && (N & (1LL << k))) { k--; ret++; }
    return ret;
}
int popcount(int N) { return __builtin_popcountll(N); }
int unpopcount(int N) { return 64 - __builtin_clzll(N) - __builtin_popcountll(N); }

int top_bit(int N) { return 63 - __builtin_clzll(N);} // 2^kの位
int bot_bit(int N) { return __builtin_ctz(N);} // 2^kの位
int MSB(int N) { return 1 << (63 - __builtin_clzll(N)); } // mask
// LSBどこいった?

int bit_width(int N) { return 64 - __builtin_clzll(N); } // 桁数
int ceil_log2(int N) { return 63 - __builtin_clzll(N); }
int bit_floor(int N) { return 1 << (63 - __builtin_clzll(N)); }
int floor_log2(int N) { return 64 - __builtin_clzll(N-1); }
int bit_ceil(int N) { return 1 << (64 - __builtin_clzll(N-1)) - (N==1); }

class UnionFind {
public:
	UnionFind() = default;
    UnionFind(int N) : par(N), sz(N, 1) {
        iota(par.begin(), par.end(), 0);
    }

	int root(int x) {
		if (par[x] == x) return x;
		return (par[x] = root(par[x]));
	}

	bool unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);

        if (rx == ry) return false;
		if (sz[rx] < sz[ry]) swap(rx, ry);

		sz[rx] += sz[ry];
		par[ry] = rx;

        return true;
	}

	bool issame(int x, int y) { return (root(x) == root(y)); }
	int size(int x) { return sz[root(x)]; }

    vector<vector<int>> groups(int N) {
        vector<vector<int>> G(N);
        for (int x = 0; x < N; x++) {
            G[root(x)].push_back(x);
        }
		G.erase(
            remove_if(G.begin(), G.end(),
                [&](const vector<int>& V) { return V.empty(); }),
                    G.end());
        return G;
    }
private:
	vector<int> par;
	vector<int> sz;
};

template<int mod> class Modint{
public:
    int val = 0;
    Modint(int x = 0) { while (x < 0) x += mod; val = x % mod; }
    Modint(const Modint &r) { val = r.val; }

    Modint operator -() { return Modint(-val); } // 単項
    Modint operator +(const Modint &r) { return Modint(*this) += r; }
    Modint operator +(const int &q) { Modint r(q); return Modint(*this) += r; }
    Modint operator -(const Modint &r) { return Modint(*this) -= r; }
    Modint operator -(const int &q) { Modint r(q); return Modint(*this) -= r; }
    Modint operator *(const Modint &r) { return Modint(*this) *= r; }
    Modint operator *(const int &q) { Modint r(q); return Modint(*this) *= r; }
    Modint operator /(const Modint &r) { return Modint(*this) /= r; }
    Modint operator /(const int &q) { Modint r(q); return Modint(*this) /= r; }
    
    Modint& operator ++() { val++; if (val >= mod) val -= mod; return *this; } // 前置
    Modint operator ++(signed) { ++*this; return *this; } // 後置
    Modint& operator --() { val--; if (val < 0) val += mod; return *this; }
    Modint operator --(signed) { --*this; return *this; }
    Modint &operator +=(const Modint &r) { val += r.val; if (val >= mod) val -= mod; return *this; }
    Modint &operator +=(const int &q) { Modint r(q); val += r.val; if (val >= mod) val -= mod; return *this; }
    Modint &operator -=(const Modint &r) { if (val < r.val) val += mod; val -= r.val; return *this; }
    Modint &operator -=(const int &q) { Modint r(q);  if (val < r.val) val += mod; val -= r.val; return *this; }
    Modint &operator *=(const Modint &r) { val = val * r.val % mod; return *this; }
    Modint &operator *=(const int &q) { Modint r(q); val = val * r.val % mod; return *this; }
    Modint &operator /=(const Modint &r) {
        int a = r.val, b = mod, u = 1, v = 0;
        while (b) {int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);}
        val = val * u % mod; if (val < 0) val += mod;
        return *this;
    }
    Modint &operator /=(const int &q) {
        Modint r(q); int a = r.val, b = mod, u = 1, v = 0;
        while (b) {int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v);}
        val = val * u % mod; if (val < 0) val += mod;
        return *this;
    }

    bool operator ==(const Modint& r) { return this -> val == r.val; }
    bool operator <(const Modint& r) { return this -> val < r.val; }
    bool operator >(const Modint& r) { return this -> val > r.val; }
    bool operator !=(const Modint& r) { return this -> val != r.val; }
};

using mint = Modint<MOD>;
// using Mint = modint998244353;

istream &operator >>(istream &is, mint& x) {
    int t; is >> t;
    x = t;
    return (is);
}
ostream &operator <<(ostream &os, const mint& x) {
    return os << x.val;
}
mint modpow(const mint &x, int n) {
    // TODO: n <= -1
    if (n == 0) return 1;
    mint t = modpow(x, n / 2);
    t = t * t;
    if (n & 1) t = t * x;
    return t;
}

int modpow(__int128_t x, int n, int mod) {
    // TODO: n <= -1
    __int128_t ret = 1;
    while (n > 0) {
        if (n % 2 == 1) ret = ret * x % mod;
        x = x * x % mod;
        n /= 2;
    }
    return ret;
}

int modinv(__int128_t x, int mod) {
    if (x == 1) return 1;
    return mod - modinv(mod % x, mod) * (mod / x) % mod;
}

istream &operator >>(istream &is, __int128_t& x) {
    string S; is >> S;
    __int128_t ret = 0;
    int f = 1;
    if (S[0] == '-') f = -1; 
    for (int i = 0; i < S.length(); i++)
        if ('0' <= S[i] && S[i] <= '9')
            ret = ret * 10 + S[i] - '0';
    x = ret * f;
    return (is);
}
ostream &operator <<(ostream &os, __int128_t x) {
    ostream::sentry s(os);
    if (s) {
        __uint128_t tmp = x < 0 ? -x : x;
        char buffer[128];
        char *d = end(buffer);

        do {
            --d;
            *d = "0123456789"[tmp % 10];
            tmp /= 10;
        } while (tmp != 0);

        if (x < 0) {
            --d;
            *d = '-';
        }
        int len = end(buffer) - d;

        if (os.rdbuf()->sputn(d, len) != len) {
            os.setstate(ios_base::badbit);
        }
    }
    return os;
}

__int128_t stoll(string &S) {
    __int128_t ret = 0;
    int f = 1;
    if (S[0] == '-') f = -1; 
    for (int i = 0; i < S.length(); i++)
        if ('0' <= S[i] && S[i] <= '9')
            ret = ret * 10 + S[i] - '0';
    return ret * f;
}
__int128_t gcd(__int128_t a, __int128_t b) {
    return b ? gcd(b, a % b) : a;
}
__int128_t lcm(__int128_t a, __int128_t b) {
    return a / gcd(a, b) * b;
    // lcmが__int128_tに収まる必要あり
}

string to_string(__int128_t x) {
    string ret = "";
    if (x < 0) {
        ret += "-";
        x *= -1;
    }
    while (x) {
        ret += (char)('0' + x % 10);
        x /= 10;
    }
    reverse(ret.begin(), ret.end());
    return ret;
}
string to_string(char c) { // バグってる?
    string s = {c};
    return s;
}

vector<mint> _fac, _finv, _inv;
void COMinit(int N) {
    _fac.resize(N + 1);
    _finv.resize(N + 1);
    _inv.resize(N + 1);
    _fac[0] = _fac[1] = 1;
    _finv[0] = _finv[1] = 1;
    _inv[1] = 1;
    for (int i = 2; i <= N; i++) {
        _fac[i] = _fac[i-1] * mint(i);
        _inv[i] = -_inv[MOD % i] * mint(MOD / i);
        _finv[i] = _finv[i - 1] * _inv[i];
    }
}

mint FAC(int N) {
    if (N < 0) return 0;
    return _fac[N];
}
mint COM(int N, int K) {
    if (N < K) return 0;
    if (N < 0 or K < 0) return 0;
    return _fac[N] * _finv[K] * _finv[N - K];
}
mint PERM(int N, int K) {
    if (N < K) return 0;
    if (N < 0 or K < 0) return 0;
    return _fac[N] *  _finv[N - K];
}
mint NHK(int N, int K) {
    if (N == 0 && K == 0)  return 1;
    return COM(N + K - 1, K);
}

#pragma endregion

template<typename monoid, typename Val, typename Lazy>
struct sparse_lazy_segment_tree {
private:
    struct node{
        int lx, rx;
        node *l, *r;
        Val sum;
        Lazy lazy;
        node(int lx, int rx, Val val): lx(lx), rx(rx),
        l(nullptr), r(nullptr), sum(val), lazy(monoid::template id2<Lazy>()) {}
    };
    node *make_node(int lx, int rx, Val val = monoid::template id1<Val>()) {
        return new node(lx, rx, val);
    }
    void propagate(node *v, Lazy x) {
        v->sum = monoid::template apply<Val, Lazy>(v->sum, x, v->lx, v->rx);
        v->lazy = monoid::template propagate<Lazy>(v->lazy, x);
    }
    void push_down(node *v) {
        if (v->lazy == monoid::template id2<Lazy>()) return;
        int mid = ((int)v->lx + v->rx) >> 1;
        if (!v->l) v->l = make_node(v->lx, mid);
        if (!v->r) v->r = make_node(mid, v->rx);
        propagate(v->l, v->lazy);
        propagate(v->r, v->lazy);
        v->lazy = monoid::template id2<Lazy>();
    }
    Val set(node *v, int k, Val x) {
        if (v->rx - v->lx == 1) return v->sum = x;
        push_down(v);
        int mid = ((int)v->lx + v->rx) >> 1;
        if (mid <= k) {
        if (!v->r) v->r = make_node(mid, v->rx);
        if (!v->l) return v->sum = set(v->r, k, x);
        else return v->sum = monoid::template merge<Val>(v->l->sum, set(v->r, k, x));
        } else {
            if (!v->l) v->l = make_node(v->lx, mid);
            if (!v->r) return v->sum = set(v->l, k, x);
            else return v->sum = monoid::template merge<Val>(set(v->l, k, x), v->r->sum);
        }
    }
    Val get(node *v, int k) {
        if (!v) return monoid::template id1<Val>();
        if (v->rx - v->lx == 1) return v->sum;
        push_down(v);
        int mid = ((int)v->lx + v->rx) >> 1;
        if (mid <= k) return get(v->r, k);
        else return get(v->l, k);
    }
    Val apply(node *v, int l, int r, Lazy x) {
        if (r <= v->lx || v->rx <= l) return v->sum;
        if (l <= v->lx && v->rx <= r) {
            propagate(v, x);
            return v->sum;
        }
        push_down(v);
        int mid = ((int)v->lx + v->rx) >> 1;
        if (!v->l) v->l = make_node(v->lx, mid);
        if (!v->r) v->r = make_node(mid, v->rx);
        return v->sum = monoid::template merge<Val>(apply(v->l, l, r, x), apply(v->r, l, r, x));
    }
    Val prod(node *v, int l, int r) {
        if (!v || r <= v->lx || v->rx <= l) return monoid::template id1<Val>();
        if (l <= v->lx && v->rx <= r) return v->sum;
        push_down(v);
        return monoid::template merge<Val>(prod(v->l, l, r), prod(v->r, l, r));
    }
    template<typename F>
    pair<int, Val> bisect_from_left(node *v, const int l, const F &f, Val ok) {
        if (v->rx <= l) return {-1, ok};
        push_down(v);
        if (l <= v->lx) {
            Val m = monoid::template merge<Val>(ok, v->sum);
            if (!f(m)) return {-1, m};
            if (v->rx - v->lx == 1) return {v->lx, m};
        }
        pair<int, Val> x{-1, monoid::template id1<Val>()};
        if (v->l) x = bisect_from_left(v->l, l, f, ok);
        if (x.first != -1) return x;
        if (v->r) x = bisect_from_left(v->r, l, f, ok);
        return x;
    }
    template<typename F>
    pair<int, Val> bisect_from_right(node *v, const int r, const F &f, Val ok) {
        if (r < v->lx) return {-1, ok};
        push_down(v);
        if (v->rx <= r + 1) {
            Val m = monoid::template merge<Val>(v->sum, ok);
            if (!f(m)) return {-1, m};
            if (v->rx - v->lx == 1) return {v->lx, m};
        }
        pair<int, Val> x{-1, monoid::template id1<Val>()};
        if (v->r) x = bisect_from_right(v->r, r, f, ok);
        if (x.first != -1) return x;
        if (v->l) x = bisect_from_right(v->l, r, f, ok);
        return x;
    }
    node *root;
public:
    sparse_lazy_segment_tree(): root(nullptr) {}
    sparse_lazy_segment_tree(int min_x, int max_x) {
        root = make_node(min_x, max_x);
    }
    void set(int i, Val x) {
        assert(root);
        set(root, i, x);
    }
    void add(int i, Val x) {
        assert(root);
        set(root, i, get(i) + x);
    }
    Val get(int i) {
        assert(root);
        return get(root, i);
    }
    void apply(int l, int r, Lazy x) {
        assert(root);
        apply(root, l, r, x);
    }
    Val prod(int l, int r) {
        assert(root);
        return prod(root, l, r);
    }
    Val all_prod() {
        assert(root);
        return root->sum;
    }
    // f(sum[l, r])がtrueになる最左のr. ない場合は-1
    template<typename F>
    int bisect_from_left(int l, const F &f) {
        assert(root && root->lx <= l && l < root->rx);
        assert(!f(monoid::template id<Val>()));
        return bisect_from_left(root, l, f, monoid::template id1<Val>()).first;
    }
    // f(sum[l, r])がtrueになる最右のl. ない場合は-1
    template<typename F>
    int bisect_from_right(int r, const F &f) {
        assert(root && root->lx <= r && r < root->rx);
        assert(!f(monoid::template id<Val>()));
        return bisect_from_right(root, r, f, monoid::template id1<Val>()).first;
    }
};

struct range_add_range_sum{
    template<typename T>
    static T id1() {
        return T(0);
    }
    template<typename E>
    static E id2() {
        return E(0);
    }
    template<typename T>
    static T merge(T a, T b) {
        return a + b;
    }
    template<typename T, typename E>
    static T apply(T a, E b, int l, int r) {
        return a + b * (r - l);
    }
    template<typename E>
    static E propagate(E a, E b) {
        return a + b;
    }
};

template<class T, bool Strict=false> class UpdateInterval {
public:
	map<int, T> interval; // (左端、値)
	UpdateInterval(const T& sentinel)
	 	: interval({{-INFL, sentinel}}) {} // 左端-INFL, 値sentinelで初期化
	void update(const int &left, const int &right, const T &_data) {
		auto st = interval.lower_bound(left);
		auto ed = interval.lower_bound(right);
		bool add = (ed == interval.end() or ed->first != right);
        bool _update = ((--st)->second != _data);
		const T kp = (--ed)->second;
		interval.erase(++st, ++ed);
		if (!Strict or _update) interval.emplace(left, _data);
		if (add) {
			if (!Strict or (kp != _data)) interval.emplace(right, kp);
		} else if (Strict) {
			ed = interval.lower_bound(right);
			if (ed->second == _data) interval.erase(ed);
		}
	}
	T& get(const int &pos) {
		auto it = interval.upper_bound(pos);
		return (--it)->second;
	}
};

signed main() {
    int N;
    cin >> N;

    unordered_map<string, int> mp;

    sparse_lazy_segment_tree<range_add_range_sum, int, int> tot(0, 1000000001);
    vector<UpdateInterval<int>> seg(N + 1e5 + 1, UpdateInterval<int>(0));

    int cnt = 1;
    for (int i = 0; i < N; i++) {
        string x;
        int l, r;
        cin >> x >> l >> r;
        l--; r--;
        if (mp[x] == 0) {
            mp[x] = cnt;
            cnt++;
        }
        tot.apply(l, r + 1, 1);
        seg[mp[x]].update(l, r + 1, 1);
    }

    int Q;
    cin >> Q;
    for (int q = 0; q < Q; q++) {
        int t;
        cin >> t;
        if (t == 1) {
            string x;
            int time;
            cin >> x >> time;
            time--;
            if (mp[x] == 0) {
                mp[x] = cnt;
                cnt++;
            }

            if (seg[mp[x]].get(time)) cout << "Yes" << endl;
            else cout << "No" << endl;
        } else if (t == 2) {
            int time;
            cin >> time;
            time--;
            cout << tot.prod(time, time + 1) << endl;
        } else {
            string x;
            int l, r;
            cin >> x >> l >> r;
            l--; r--;
            if (mp[x] == 0) {
                mp[x] = cnt;
                cnt++;
            }

            tot.apply(l, r + 1, 1);
            seg[mp[x]].update(l, r + 1, 1);
        }
    }
}
yukicoder

結果

テストケース

ソースコード
