Submission #4353710


Source Code Expand

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

Submission Info

Submission Time
Task D - Dangerous Hopscotch
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 6321 Byte
Status
Exec Time 363 ms
Memory 11892 KB

Judge Result

Set Name Score / Max Score Test Cases
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
Case Name Status Exec Time Memory
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