提出 #4353710


ソースコード 拡げる

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
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; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
    static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
    ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
    int get() const { return (int)x; }
    ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
    ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
    ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
    ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
    ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
    ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
    ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
    ModInt inverse() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
        return ModInt(u);
    }
    bool operator==(ModInt that) const { return x == that.x; }
    bool operator!=(ModInt that) const { return x != that.x; }
    ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
    ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r;
}
typedef ModInt<1000000007> mint;
struct func {
    mint m[2][2];
    func() {
        rep(i, 0, 2) rep(j, 0, 2) m[i][j] = 0;
        rep(i, 0, 2) m[i][i] = 1;
    }
    func(int flag) {

        if (flag == 0) { // 石がない
            m[0][0] = 1;
            m[0][1] = 1;
            m[1][0] = 1;
            m[1][1] = 0;
        }
        else { // 石がある
            m[0][0] = 0;
            m[0][1] = 0;
            m[1][0] = 1;
            m[1][1] = 0;
        }
    }
};
func mul(func x, func y) {
    func res;
    rep(i, 0, 2) rep(j, 0, 2) res.m[i][j] = 0;
    rep(i, 0, 2) rep(j, 0, 2) rep(k, 0, 2) {
        res.m[i][j] = (res.m[i][j] + x.m[i][k] * y.m[k][j]);
    }
    return res;
}
func operator*(func y, func x) {
    return mul(x, y);
}
//---------------------------------------------------------------------------------------------------
template<class V, int NV> struct SegTree { // [L,R)
    V comp(V l, V r) { return l * r; };
    vector<V> val; SegTree() { val = vector<V>(NV * 2); }
    V get(int x, int y, int l = 0, int r = NV, int k = 1) {
        if (r <= x || y <= l)return V(); if (x <= l && r <= y)return val[k]; auto A = get(x, y, l, (l + r) / 2, k * 2);
        auto B = get(x, y, (l + r) / 2, r, k * 2 + 1); return comp(A, B);
    }
    void update(int i, V v) { i += NV; val[i] = v; while (i > 1)i >>= 1, val[i] = comp(val[i * 2], val[i * 2 + 1]); }
};
/*---------------------------------------------------------------------------------------------------
            ∧_∧  
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i     
    /   \     | |     
    /   / ̄ ̄ ̄ ̄/  |  
  __(__ニつ/     _/ .| .|____  
     \/____/ (u ⊃  
---------------------------------------------------------------------------------------------------*/






int N, Q;
int T[101010], X[101010], Y[101010];
int A[101010];
SegTree<func, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
vector<int> dic;
func get(int len, int stone) {
    func f(0), x(0);
    func ret;
    while (0 < len) {
        if ((len % 2) == 0) x = mul(x, x), len >>= 1;
        else ret = mul(ret, x), --len;
    }
    if (stone == 1) {
        ret.m[0][0] = 0;
        ret.m[0][1] = 0;
    }
    return ret;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;

    rep(i, 0, Q) {
        cin >> T[i];
        if (T[i] == 1) {
            cin >> X[i];
            dic.push_back(X[i]);
        }
        else {
            cin >> X[i] >> Y[i];
            dic.push_back(X[i]);
            dic.push_back(Y[i]);
        }
    }

    sort(all(dic));
    dic.erase(unique(all(dic)), dic.end());

    int n = dic.size();
    rep(i, 0, n - 1) {
        st.update(i, get(dic[i + 1] - dic[i], 0));
    }

    // st[i] := dic[i] -> dic[i+1]

    rep(q, 0, Q) {
        int t; t = T[q];
        if (t == 1) {
            int p = X[q];
            p = lower_bound(all(dic), p) - dic.begin();

            if (A[p] == 0) {
                A[p] = 1;
                if(0 < p) st.update(p-1, get(dic[p]-dic[p-1], A[p]));
            }
            else {
                A[p] = 0;
                if (0 < p) st.update(p-1, get(dic[p] - dic[p - 1], A[p]));
            }
        }
        else {
            int l, r; l = X[q], r = Y[q];

            l = lower_bound(all(dic), l) - dic.begin();
            r = lower_bound(all(dic), r) - dic.begin();

            if (A[l] == 1) {
                printf("0\n");
                continue;
            }

            func f = st.get(l, r);

            printf("%d\n", f.m[0][0].get());
        }
    }
}

提出情報

提出日時
問題 D - Dangerous Hopscotch
ユーザ hamayanhamayan
言語 C++14 (GCC 5.4.1)
得点 0
コード長 6321 Byte
結果
実行時間 363 ms
メモリ 11892 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 01.txt, 02.txt
All 0 / 900 01.txt, 02.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt
ケース名 結果 実行時間 メモリ
01.txt 5 ms 8448 KB
02.txt 5 ms 8448 KB
11.txt 5 ms 8448 KB
12.txt 5 ms 8448 KB
13.txt 5 ms 8448 KB
14.txt 293 ms 11124 KB
15.txt 293 ms 11124 KB
16.txt 292 ms 11252 KB
17.txt 79 ms 10616 KB
18.txt 79 ms 10616 KB
19.txt 64 ms 10616 KB
20.txt 64 ms 10616 KB
21.txt 119 ms 10616 KB
22.txt 119 ms 10616 KB
23.txt 119 ms 10616 KB
24.txt 119 ms 10616 KB
25.txt 119 ms 10616 KB
26.txt 232 ms 10616 KB
27.txt 232 ms 10616 KB
28.txt 232 ms 10616 KB
29.txt 232 ms 10616 KB
30.txt 232 ms 10616 KB
31.txt 359 ms 11892 KB
32.txt 363 ms 11892 KB
33.txt 357 ms 11892 KB
34.txt 358 ms 11892 KB
35.txt 358 ms 11892 KB
36.txt 294 ms 11252 KB
37.txt 295 ms 11252 KB
38.txt 299 ms 11252 KB
39.txt 294 ms 11252 KB
40.txt 297 ms 11252 KB