Submission #1514495

---

Source Code Expand

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
#define ALL(X) X.begin(), X.end()
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef std::pair<LL,LL> PLL;//
typedef std::pair<int,int> PII;//
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18+20;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int H;
	LL W;
	cin >> H >> W;
	if( W > 100000 ) return;
	int N;
	cin >> N;
	set< pair<LL,LL> > used;
	set< pair<LL,LL> >::iterator itr;
	pair<LL,LL> temp;
	temp.first = 0;
	temp.second = W+1;
	used.insert( temp );
	temp.first = 1;
	used.insert( temp );//番兵

	vector<LL> dp(4,0),next(4);
	dp[0] = 1;
	
	while(N--){
		cin >> temp.first >> temp.second;
		temp.first--;
		itr = used.find( temp );
		if( itr != used.end() ){//使用済みなので外す
			used.erase( itr );
		}else{//未使用なのでつける
			used.insert( temp );
		}
		dp.assign(4,0);
		dp[0] = 1;
		vector< vector<bool> > cap(2,vector<bool>(2,false));
		temp.first = 0;temp.second = 1;
		if( used.find(temp) != used.end() ){cap[0][0] = true;}
		temp.first = 1;
		if( used.find(temp) != used.end() ){cap[0][1] = true;}
		for(LL i=1;i<=W;++i){
			temp.first = 0;
			temp.second = i+1;
			itr = used.find( temp );
			if( itr == used.end() ){
				cap[0][1] = false;
			}else{
				cap[0][1] = true;
			}
			temp.first = 1;
			itr = used.find( temp );
			if( itr == used.end() ){
				cap[1][1] = false;
			}else{
				cap[1][1] = true;
			}
			//////
			for(int k=0;k<4;++k){
				if( dp[k] == 0 ) continue;
				next[0] = (next[0] + dp[k]) % MOD;
				int count = 0;
				if( (k&1)==0 && cap[0][0] == false && cap[0][1] == false ){
					++count;
					next[1] = (next[1] + dp[k]) % MOD;//上に横
				}
				if( (k&2)==0 && cap[1][0] == false && cap[1][1] == false ){
					++count;
					next[2] = (next[2] + dp[k]) % MOD;//下に横
				}
				if( count == 2 ){
					next[3] = (next[3] + dp[k]) % MOD;//上下に横
				}
				if( k==0 && cap[0][0] == false && cap[1][0] == false ){
					next[0] = (next[0] + dp[k]) % MOD;//縦
				}
			}
			dp = next;
			next.assign(4,0);
			cap[0][0] = cap[0][1];
			cap[1][0] = cap[1][1];
		}
		LL ans = dp[0];
		cout << ans << endl;
	}
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}
#pragma endregion //main()

Submission Info

Judge Result