Submission #2893330
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
void read(pp& x){ scanf("%d%d",&x.first, &x.second); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define sz(x) (int)(x).size()
int h, w;
const ll mod = int(1e9) + 7;
struct mat {
int N;
ll x[4][4];
mat(int N_): N(N_) {
memset(x, 0, sizeof(x));
}
mat operator*(const mat& r) const {
mat ret(N);
rep(i, N) rep(j, N) rep(k, N) (ret.x[i][j] += x[i][k] * r.x[k][j]) %= mod;
return ret;
}
mat operator+(const mat& r) const {
mat ret(N);
rep(i, N) rep(j, N) ret.x[i][j] = (x[i][j] + r.x[i][j]) % mod;
return ret;
}
} *I;
int h2;
ll crd[20010], cn;
int type[40010];
int state[40010];
const int M = 65536;
mat* tree[M<<1];
mat* induct[4];
mat* start;
pp qry[40010];
void Pow(mat* base, ll e, mat* ret){
*ret = *I;
mat tmp = *base;
while(e){
if(e&1) (*ret) = (*ret) * tmp;
e >>= 1; tmp = tmp * tmp;
}
}
void tree_set(int p, mat* v, ll e){
p += M; Pow(v, e, tree[p]);
for(p/=2;p;p/=2){
*tree[p] = *tree[p*2] * *tree[p<<1|1];
}
}
int main()
{
read(h, w); h2=(1<<h);
I = new mat(h2);
rep(i, h2) I->x[i][i] = 1;
for(int i=1; i<2*M; ++i){
tree[i] = new mat(h2);
*tree[i] = *I;
}
if(h2 == 2){
start = new mat(2);
start->x[0][1] = 1;
induct[0] = new mat(2);
induct[0]->x[0][0] = 1;
induct[0]->x[1][0] = 1;
induct[0]->x[0][1] = 1;
induct[1] = new mat(2);
induct[1]->x[0][1] = 1;
induct[1]->x[1][1] = 1;
} else {
start = new mat(4);
start->x[0][3] = 1;
induct[3] = new mat(4);
rep(i,4) induct[3]->x[i][3] = 1;
induct[2] = new mat(4);
rep(i,4) induct[2]->x[i][2] += 1;
induct[2]->x[0][3] += 1;
induct[2]->x[2][3] += 1;
induct[1] = new mat(4);
rep(i,4) induct[1]->x[i][1] += 1;
induct[1]->x[0][3] += 1;
induct[1]->x[1][3] += 1;
induct[0] = new mat(4);
rep(i,4) induct[0]->x[i][0] += 1, induct[0]->x[i][3] += 1;
induct[0]->x[0][2] += 1;
induct[0]->x[1][2] += 1;
induct[0]->x[0][1] += 1;
induct[0]->x[2][1] += 1;
induct[0]->x[0][3] += 1;
}
int q;
read(q);
rrep(i, q){ read(qry[i]); crd[i] = qry[i].y; }
crd[0] = 1; crd[q+1] = w;
sort(crd, crd+q+2);
cn = unique(crd, crd+q+2) - crd;
rep(i, cn-1){
tree_set(2*i+1, induct[0], crd[i+1]-crd[i]-1);
}
rep(i, cn){
tree_set(2*i, induct[0], 1);
}
rrep(i, q){
int x, y; tie(x, y) = qry[i];
y = (lower_bound(crd, crd+cn, y) - crd);
tree_set(2*y, induct[state[y] ^= (1 << (--x))], 1);
mat ret = (*start) * (*tree[1]);
printf("%lld\n", accumulate(ret.x[0], ret.x[0]+4, 0ll) % mod);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - コンセント |
User |
Namnamseo |
Language |
C++14 (GCC 5.4.1) |
Score |
40 |
Code Size |
3081 Byte |
Status |
WA |
Exec Time |
323 ms |
Memory |
20352 KB |
Compile Error
./Main.cpp: In function ‘void read(int&)’:
./Main.cpp:6:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void read(int& x){ scanf("%d",&x); }
^
./Main.cpp: In function ‘void read(ll&)’:
./Main.cpp:7:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void read(ll& x){ scanf("%lld",&x); }
^
./Main.cpp: In function ‘void read(pp&)’:
./Main.cpp:8:52: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void read(pp& x){ scanf("%d%d",&x.first, &x.second); }
^
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
10 / 10 |
30 / 30 |
0 / 60 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample-01.txt, subtask0_sample-02.txt |
Subtask1 |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt |
Subtask2 |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt |
Subtask3 |
subtask0_sample-01.txt, subtask0_sample-02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample-01.txt |
AC |
15 ms |
19712 KB |
subtask0_sample-02.txt |
AC |
15 ms |
19712 KB |
subtask1_01.txt |
AC |
15 ms |
19712 KB |
subtask1_02.txt |
AC |
15 ms |
19712 KB |
subtask1_03.txt |
AC |
16 ms |
19712 KB |
subtask1_04.txt |
AC |
17 ms |
19712 KB |
subtask1_05.txt |
AC |
38 ms |
19840 KB |
subtask1_06.txt |
AC |
38 ms |
19840 KB |
subtask1_07.txt |
AC |
22 ms |
19840 KB |
subtask1_08.txt |
AC |
43 ms |
19840 KB |
subtask1_09.txt |
AC |
41 ms |
19840 KB |
subtask1_10.txt |
AC |
41 ms |
19840 KB |
subtask2_01.txt |
AC |
34 ms |
19712 KB |
subtask2_02.txt |
AC |
32 ms |
19712 KB |
subtask2_03.txt |
AC |
24 ms |
19712 KB |
subtask2_04.txt |
AC |
22 ms |
19712 KB |
subtask2_05.txt |
AC |
25 ms |
19840 KB |
subtask2_06.txt |
AC |
49 ms |
19840 KB |
subtask2_07.txt |
AC |
50 ms |
19840 KB |
subtask2_08.txt |
AC |
25 ms |
19840 KB |
subtask2_09.txt |
AC |
49 ms |
19840 KB |
subtask2_10.txt |
AC |
49 ms |
19840 KB |
subtask3_01.txt |
WA |
320 ms |
20224 KB |
subtask3_02.txt |
AC |
307 ms |
20224 KB |
subtask3_03.txt |
AC |
98 ms |
20352 KB |
subtask3_04.txt |
WA |
323 ms |
20352 KB |
subtask3_05.txt |
WA |
102 ms |
20224 KB |
subtask3_06.txt |
WA |
102 ms |
20352 KB |
subtask3_07.txt |
WA |
320 ms |
20352 KB |
subtask3_08.txt |
WA |
319 ms |
20352 KB |
subtask3_09.txt |
WA |
319 ms |
20224 KB |
subtask3_10.txt |
WA |
318 ms |
20224 KB |