Submission #4353359


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 operator*(func y, func x) {

    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;
}
//---------------------------------------------------------------------------------------------------
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 A[101010];
SegTree<func, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) st.update(i, func(0));

    rep(q, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int p; cin >> p; p--;
            if (A[p] == 0) {
                A[p] = 1;
                st.update(p, func(1));
            }
            else {
                A[p] = 0;
                st.update(p, func(0));
            }
        }
        else {
            int l, r; cin >> l >> r;

            if (A[l-1] == 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 3469 Byte
Status
Exec Time 325 ms
Memory 4480 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 325 ms 4352 KB
14.txt 297 ms 4352 KB
15.txt 295 ms 4352 KB
16.txt 297 ms 4352 KB
17.txt 146 ms 4480 KB
18.txt 147 ms 4480 KB
19.txt 136 ms 4480 KB
20.txt 135 ms 4480 KB
21.txt 295 ms 4352 KB
22.txt 295 ms 4352 KB
23.txt 296 ms 4352 KB
24.txt 295 ms 4352 KB
25.txt 296 ms 4352 KB
26.txt 297 ms 4352 KB
27.txt 298 ms 4352 KB
28.txt 297 ms 4352 KB
29.txt 295 ms 4352 KB
30.txt 296 ms 4352 KB
31.txt 297 ms 4352 KB
32.txt 295 ms 4352 KB
33.txt 295 ms 4352 KB
34.txt 296 ms 4352 KB
35.txt 295 ms 4352 KB
36.txt 295 ms 4352 KB
37.txt 293 ms 4352 KB
38.txt 294 ms 4352 KB
39.txt 295 ms 4352 KB
40.txt 294 ms 4352 KB