Submission #4353535


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] + x.m[i][k] * y.m[k][j]) % mod;
    }
    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 << 17> 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 4663 Byte
Status
Exec Time 699 ms
Memory 6520 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 3 ms 4352 KB
02.txt 3 ms 4352 KB
11.txt 3 ms 4352 KB
12.txt 3 ms 4352 KB
13.txt 3 ms 4352 KB
14.txt 536 ms 6520 KB
15.txt 535 ms 6520 KB
16.txt 534 ms 6520 KB
17.txt 166 ms 6520 KB
18.txt 166 ms 6520 KB
19.txt 139 ms 6520 KB
20.txt 139 ms 6520 KB
21.txt 308 ms 6520 KB
22.txt 305 ms 6520 KB
23.txt 308 ms 6520 KB
24.txt 308 ms 6520 KB
25.txt 306 ms 6520 KB
26.txt 691 ms 6520 KB
27.txt 699 ms 6520 KB
28.txt 695 ms 6520 KB
29.txt 693 ms 6520 KB
30.txt 692 ms 6520 KB
31.txt 535 ms 6388 KB
32.txt 535 ms 6388 KB
33.txt 534 ms 6388 KB
34.txt 536 ms 6388 KB
35.txt 537 ms 6388 KB
36.txt 536 ms 6520 KB
37.txt 535 ms 6520 KB
38.txt 539 ms 6520 KB
39.txt 534 ms 6520 KB
40.txt 536 ms 6520 KB