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
AC × 2
AC × 12
AC × 22
AC × 24
WA × 8
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