Submission #4353637


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; }
//---------------------------------------------------------------------------------------------------
int mod = 1000000007;
struct func {
    int 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] = (1LL * res.m[i][j] + 1LL * x.m[i][k] * y.m[k][j]) % mod;
    }
    return res;
}
func operator*(func y, func x) {
    return mul(y, x);
}
//---------------------------------------------------------------------------------------------------
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]);
        }
    }
}

Submission Info

Submission Time
Task D - Dangerous Hopscotch
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4671 Byte
Status
Exec Time 1012 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 4 ms 8448 KB
02.txt 4 ms 8448 KB
11.txt 4 ms 8448 KB
12.txt 4 ms 8448 KB
13.txt 4 ms 8448 KB
14.txt 857 ms 11124 KB
15.txt 856 ms 11124 KB
16.txt 856 ms 10996 KB
17.txt 172 ms 10616 KB
18.txt 172 ms 10616 KB
19.txt 145 ms 10616 KB
20.txt 144 ms 10616 KB
21.txt 318 ms 10616 KB
22.txt 316 ms 10616 KB
23.txt 319 ms 10616 KB
24.txt 320 ms 10616 KB
25.txt 317 ms 10616 KB
26.txt 717 ms 10616 KB
27.txt 718 ms 10616 KB
28.txt 717 ms 10616 KB
29.txt 716 ms 10616 KB
30.txt 717 ms 10616 KB
31.txt 1008 ms 11892 KB
32.txt 1010 ms 11892 KB
33.txt 1010 ms 11764 KB
34.txt 1008 ms 11892 KB
35.txt 1012 ms 11892 KB
36.txt 872 ms 10996 KB
37.txt 857 ms 11124 KB
38.txt 855 ms 11124 KB
39.txt 859 ms 11124 KB
40.txt 857 ms 11124 KB