Submission #4353482


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define MD 1000000007
void *wmem;
void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
void wt_L(int x){
  char f[10];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int fibonacci_mod_L(unsigned long long n, int md){
  unsigned long long a=1, b=0, c=1, ma=1, mb=1, mc=0, ta, tb, tc;
  while(n){
    if(n%2){
      ta = a*ma + b*mb;
      tb = a*mb + b*mc;
      tc = b*mb + c*mc;
      a = ta % md;
      b = tb % md;
      c = tc % md;
    }
    ta = ma*ma + mb*mb;
    tb = ma*mb + mb*mc;
    tc = mb*mb + mc*mc;
    ma = ta % md;
    mb = tb % md;
    mc = tc % md;
    n/=2;
  }
  return b;
}
template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){
  int i, k=0;
  pair<T,int> *r=(pair<T,int>*)mem;
  for(i=0;i<n;i++){
    r[i].first = arr[i];
    r[i].second = i;
  }
  sort(r, r+n);
  if(res != NULL){
    for(i=0;i<n;i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      res[r[i].second] = k;
    }
  }
  else{
    for(i=0;i<n;i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      arr[r[i].second] = k;
    }
  }
  return k+1;
}
char memarr[96000000];
int L[100000], N, P[100000], Q, R[100000], TYPE[100000], arr[1000000], lef[2000000], mat[2000000][4], mat_ng[4], mat_ok[4], red[1000000], rig[2000000], tmparr1[4], tmparr2[4], us, use[1000000], v1[2000000], v2[2000000], val[1000000];
map<int,int> cnv, stone;
void multi(int a[], int b[], int res[]){
  res[0] = ((long long)a[0] * b[0] + (long long)a[1] * b[2]) % MD;
  res[1] = ((long long)a[0] * b[1] + (long long)a[1] * b[3]) % MD;
  res[2] = ((long long)a[2] * b[0] + (long long)a[3] * b[2]) % MD;
  res[3] = ((long long)a[2] * b[1] + (long long)a[3] * b[3]) % MD;
}
void getmat(int n, int res[]){
  int i;
  for(i=0;i<4;i++){
    res[i] = 0;
  }
  if(n==0){
    res[0] = res[3] = 1;
  }
  else{
    res[0] =fibonacci_mod_L(n+1, MD);
    res[1] = res[2] =fibonacci_mod_L(n, MD);
    res[3] =fibonacci_mod_L(n-1, MD);
  }
}
void gen(int node, int a, int b){
  int hf, n1, n2, sz;
  n1 = node * 2 + 1;
  n2 = node * 2 + 2;
  sz = b - a;
  hf = a + sz / 2;
  if(sz == 1){
    getmat(val[a+1]-val[a], mat[node]);
  }
  else{
    gen(n1, a, hf);
    gen(n2, hf, b);
    multi(mat[n1], mat[n2], mat[node]);
  }
}
void change(int node, int n, int a, int b){
  int hf, len, n1, n2, sz;
  n1 = node * 2 + 1;
  n2 = node * 2 + 2;
  sz = b - a;
  hf = a + sz / 2;
  if(n < a || n >= b){
    return;
  }
  if(sz > 1){
    change(n1, n, a, hf);
    change(n2, n, hf, b);
    multi(mat[n1], mat[n2], mat[node]);
  }
  else{
    len = val[n+1] - val[n];
    if(stone[n]==1){
      int i;
      for(i=0;i<4;i++){
        tmparr1[i] = mat_ng[i];
      }
    }
    else{
      int i;
      for(i=0;i<4;i++){
        tmparr1[i] = mat_ok[i];
      }
    }
    if(len > 1){
      getmat(len-1, tmparr2);
      multi(tmparr1,tmparr2,mat[node]);
    }
    else{
      int i;
      for(i=0;i<4;i++){
        mat[node][i] = tmparr1[i];
      }
    }
  }
}
void get(int node, int l, int r, int a, int b, int *res){
  int hf, i, n1, n2, *send1, *send2, sz;
  n1 = node * 2 + 1;
  n2 = node * 2 + 2;
  sz = b - a;
  hf = a + sz / 2;
  if(l < a){
    l = a;
  }
  if(r > b){
    r = b;
  }
  if(l >= r){
    getmat(0,res);
    return;
  }
  if(l==a && r==b){
    for(i=0;i<4;i++){
      res[i] = mat[node][i];
    }
    return;
  }
  send1 = res+4;
  get(n1, l, r, a, hf, send1);
  send2 = send1 + 4;
  get(n2, l, r, hf, b, send2);
  multi(send1,send2,res);
}
int main(){
  int i, j, k, uus;
  wmem = memarr;
  rd(N);
  rd(Q);
  us = 0;
  for(i=0;i<Q;i++){
    rd(TYPE[i]);
    if(TYPE[i]==1){
      rd(P[i]);
      use[us++] = P[i];
    }
    else{
      rd(L[i]);
      rd(R[i]);
      use[us++] = L[i];
      use[us++] = R[i];
    }
  }
  use[us++] = N+1;
  uus = us;
  us =coordcomp_L(us, use, red);
  for(i=0;i<uus;i++){
    cnv[use[i]] = red[i];
  }
  for(i=0;i<uus;i++){
    val[red[i]] = use[i];
  }
  val[us] = N+10;
  getmat(1, mat_ok);
  getmat(1, mat_ng);
  mat_ng[0] = 0;
  mat_ng[1] = 0;
  gen(0, 0, us);
  for(i=0;i<Q;i++){
    if(TYPE[i]==1){
      P[i] = cnv[P[i]];
      if(stone.count(P[i])==0){
        stone[P[i]] = 0;
      }
      stone[P[i]] = 1 - stone[P[i]];
      change(0, P[i], 0, us);
    }
    else{
      L[i] = cnv[L[i]];
      R[i] = cnv[R[i]];
      if(stone.count(L[i]) && stone[L[i]]==1){
        wt_L(0);
        putchar_unlocked('\n');
        continue;
      }
      if(stone.count(R[i]) && stone[R[i]]==1){
        wt_L(0);
        putchar_unlocked('\n');
        continue;
      }
      get(0, L[i], R[i], 0, us, arr);
      wt_L(arr[0]);
      putchar_unlocked('\n');
    }
  }
  return 0;
}
// cLay varsion 20180730-1

// --- original code ---
// int N, Q, TYPE[1d5], P[1d5], L[1d5], R[1d5];
// 
// int use[1d6], red[1d6], val[1d6], us;
// 
// int v1[2d6], v2[2d6];
// int lef[2d6], rig[2d6];
// int mat[2d6][4];
// 
// int mat_ok[4], mat_ng[4];
// 
// map<int,int> stone;
// 
// 
// void multi(int a[], int b[], int res[]){
//   res[0] = ((ll)a[0] * b[0] + (ll)a[1] * b[2]) % MD;
//   res[1] = ((ll)a[0] * b[1] + (ll)a[1] * b[3]) % MD;
//   res[2] = ((ll)a[2] * b[0] + (ll)a[3] * b[2]) % MD;
//   res[3] = ((ll)a[2] * b[1] + (ll)a[3] * b[3]) % MD;
// }
// 
// void getmat(int n, int res[]){
//   int i;
//   rep(i,4) res[i] = 0;
//   if(n==0){
//     res[0] = res[3] = 1;
//   } else {
//     res[0] = fib_mod(n+1);
//     res[1] = res[2] = fib_mod(n);
//     res[3] = fib_mod(n-1);
//   }
// }
// 
// 
// 
// void gen(int node, int a, int b){
//   int n1, n2, sz, hf;
// 
//   n1 = node * 2 + 1;
//   n2 = node * 2 + 2;
//   sz = b - a;
//   hf = a + sz / 2;
// 
//   if(sz == 1){
//     getmat(val[a+1]-val[a], mat[node]);
//   } else {
//     gen(n1, a, hf);
//     gen(n2, hf, b);
//     multi(mat[n1], mat[n2], mat[node]);
//   }
// }
// 
// int tmparr1[4], tmparr2[4];
// void change(int node, int n, int a, int b){
//   int n1, n2, sz, hf, len;
// 
//   n1 = node * 2 + 1;
//   n2 = node * 2 + 2;
//   sz = b - a;
//   hf = a + sz / 2;
// 
//   if(n < a || n >= b) return;
//   if(sz > 1){
//     change(n1, n, a, hf);
//     change(n2, n, hf, b);
//     multi(mat[n1], mat[n2], mat[node]);
//   } else {
//     len = val[n+1] - val[n];
//     if(stone[n]==1){
//       rep(i,4) tmparr1[i] = mat_ng[i];
//     } else {
//       rep(i,4) tmparr1[i] = mat_ok[i];
//     }
//     if(len > 1){
//       getmat(len-1, tmparr2);
//       multi(tmparr1,tmparr2,mat[node]);
//     } else {
//       rep(i,4) mat[node][i] = tmparr1[i];
//     }
//   }
// }
// 
// void get(int node, int l, int r, int a, int b, int *res){
//   int i;
//   int n1, n2, sz, hf;
//   int *send1, *send2;
// 
//   n1 = node * 2 + 1;
//   n2 = node * 2 + 2;
//   sz = b - a;
//   hf = a + sz / 2;
// 
//   if(l < a) l = a;
//   if(r > b) r = b;
//   if(l >= r){
//     getmat(0,res);
//     return;
//   }
// 
//   if(l==a && r==b){
//     rep(i,4) res[i] = mat[node][i];
//     return;
//   }
// 
//   send1 = res+4;
//   get(n1, l, r, a, hf, send1);
//   send2 = send1 + 4;
//   get(n2, l, r, hf, b, send2);
//   multi(send1,send2,res);
// }
// 
// 
// 
// int arr[1000000];
// map<int,int> cnv;
// 
// {
//   int i, j, k, uus;
// 
//   rd(N,Q);
//   us = 0;
//   rep(i,Q){
//     rd(TYPE[i]);
//     if(TYPE[i]==1){
//       rd(P[i]);
//       use[us++] = P[i];
//     } else {
//       rd(L[i],R[i]);
//       use[us++] = L[i];
//       use[us++] = R[i];
//     }
//   }
// 
//   use[us++] = N+1;
//   uus = us;
//   us = coordcomp(us, use, red);
// 
//   rep(i,uus) cnv[use[i]] = red[i];
//   rep(i,uus) val[red[i]] = use[i];
//   val[us] = N+10;
// 
//   getmat(1, mat_ok);
//   getmat(1, mat_ng);
//   mat_ng[0] = 0;
//   mat_ng[1] = 0;
// 
//   gen(0, 0, us);
//   rep(i,Q){
//     if(TYPE[i]==1){
//       P[i] = cnv[P[i]];
//       if(stone.count(P[i])==0) stone[P[i]] = 0;
//       stone[P[i]] = 1 - stone[P[i]];
//       change(0, P[i], 0, us);
//     } else {
//       L[i] = cnv[L[i]];
//       R[i] = cnv[R[i]];
//       if(stone.count(L[i]) && stone[L[i]]==1){
//         wt(0); continue;
//       }
//       if(stone.count(R[i]) && stone[R[i]]==1){
//         wt(0); continue;
//       }
//       get(0, L[i], R[i], 0, us, arr);
//       wt(arr[0]);
//     }
//   }
//   
// }

Submission Info

Submission Time
Task D - Dangerous Hopscotch
User LayCurse
Language C++14 (GCC 5.4.1)
Score 900
Code Size 8694 Byte
Status
Exec Time 527 ms
Memory 33920 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 01.txt, 02.txt
All 900 / 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 12544 KB
02.txt 3 ms 12544 KB
11.txt 3 ms 12544 KB
12.txt 3 ms 12544 KB
13.txt 3 ms 12544 KB
14.txt 502 ms 33152 KB
15.txt 510 ms 33024 KB
16.txt 526 ms 33152 KB
17.txt 63 ms 14720 KB
18.txt 63 ms 14720 KB
19.txt 32 ms 14720 KB
20.txt 32 ms 14720 KB
21.txt 169 ms 14848 KB
22.txt 168 ms 14848 KB
23.txt 169 ms 14848 KB
24.txt 169 ms 14848 KB
25.txt 168 ms 14848 KB
26.txt 471 ms 28544 KB
27.txt 469 ms 28544 KB
28.txt 473 ms 28544 KB
29.txt 474 ms 28544 KB
30.txt 469 ms 28544 KB
31.txt 510 ms 33792 KB
32.txt 519 ms 33792 KB
33.txt 511 ms 33792 KB
34.txt 527 ms 33792 KB
35.txt 522 ms 33920 KB
36.txt 508 ms 33280 KB
37.txt 510 ms 33152 KB
38.txt 504 ms 33280 KB
39.txt 504 ms 33152 KB
40.txt 507 ms 33280 KB