Submission #388158

#	Time	Username	Problem	Language	Result	Execution time	Memory
388158		Nima_Naderi	Plus Minus (BOI17_plusminus)	C++14	100 / 100	113 ms	16440 KiB

plusminus

//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll MXN = 3e5 + 10;
const ll Mod = 1e9 + 7;
ll power(ll a, ll b){
	return (!b ? 1 : power(a * a % Mod, b / 2) * (b & 1LL ? a : 1) % Mod);
}
ll n, m, k, ans;
ll X[MXN], Y[MXN], sg[MXN];
vector<ll> Num[2];
vector<pair<ll, ll>> vec[MXN];
string sgm = "+-";
bool ok, okc, okr;
ll GetId(ll f, ll x){
	return lower_bound(Num[f].begin(), Num[f].end(), x) - Num[f].begin();
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	if(k == 0){
		cout << (power(2, n) + power(2, m) - 2 + Mod) % Mod << '\n';
		return 0;
	}
	for(int i = 1; i <= k; i ++){
		char ch; cin >> ch >> X[i] >> Y[i];
		sg[i] = (ch == '-' ? -1 : +1);
		Num[0].push_back(X[i]), Num[1].push_back(Y[i]);
	}
	sort(Num[0].begin(), Num[0].end()), sort(Num[1].begin(), Num[1].end());
	Num[0].resize(unique(Num[0].begin(), Num[0].end()) - Num[0].begin());
	Num[1].resize(unique(Num[1].begin(), Num[1].end()) - Num[1].begin());
	ok = true;
	for(int i = 1; i <= k; i ++) vec[GetId(0, X[i])].emplace_back(Y[i], sg[i]);
	for(int i = 0; i < Num[0].size(); i ++){
		ll zoj = (vec[i][0].first % 2 ? -1 : +1) * vec[i][0].second;
		for(auto X : vec[i]){
			if(X.first % 2) ok &= (X.second != zoj);
			else			ok &= (X.second == zoj);
			if(!ok) break;
		}
		if(!ok) break;
	}
	okr = ok;
	if(ok){
		ans += power(2, n - int(Num[0].size()));		
	}
	ok = true;
	for(int i = 0; i < Num[0].size(); i ++) vec[i].clear();
	for(int i = 1; i <= k; i ++) vec[GetId(1, Y[i])].emplace_back(X[i], sg[i]);
	for(int i = 0; i < Num[1].size(); i ++){
		ll zoj = (vec[i][0].first % 2 ? -1 : +1) * vec[i][0].second;
		for(auto X : vec[i]){
			if(X.first % 2) ok &= (X.second != zoj);
			else			ok &= (X.second == zoj);
			if(!ok) break;
		}
		if(!ok) break;
	}
	okc = ok;
	if(ok){
		ans += power(2, m - int(Num[1].size()));		
	}
	if(okr && okc) ans = (ans - 1 + Mod) % Mod;
	cout << ans << '\n';
	return 0;
}
//! This is NIMA !

Compilation message (stderr)

plusminus.cpp: In function 'int main()':
plusminus.cpp:37:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for(int i = 0; i < Num[0].size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~
plusminus.cpp:51:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for(int i = 0; i < Num[0].size(); i ++) vec[i].clear();
      |                 ~~^~~~~~~~~~~~~~~
plusminus.cpp:53:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |  for(int i = 0; i < Num[1].size(); i ++){
      |                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 42 / 42
• Subtask 3: 46 / 46