Submission #894088

#	Time	Username	Problem	Language	Result	Execution time	Memory
894088		OAleksa	Plus Minus (BOI17_plusminus)	C++14	100 / 100	201 ms	25936 KiB

plusminus

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
const int N = 1e5 + 69;
const int mod = 1e9 + 7;
int n, m, k;
int x[N], y[N];
char c[N];
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
  int tt = 1;
  //cin >> tt;
  while (tt--) {
		cin >> n >> m >> k;
		for (int i = 1;i <= k;i++) 
			cin >> c[i] >> x[i] >> y[i];
		map<int, vector<pair<int, char>>> sv, sv1;
		for (int i = 1;i <= k;i++) {
			sv[x[i]].push_back({y[i], c[i]});
			sv1[y[i]].push_back({x[i], c[i]});
		}
		int ans = 0;
		auto mul = [&](int x, int y) {
			x *= y;
			if (x >= mod)
				x %= mod;
			return x;
		};
		auto binpow = [&](int a, int b) {
			int res = 1;
			while (b > 0) {
				if (b & 1)
					res = mul(res, a);
				a = mul(a, a);
				b >>= 1;
			}
			return res;
		};
		int pr = 0, g = 1;
		for (auto u : sv) {
			int p = u.f - pr - 1;
			g = mul(g, binpow(2, p));
			int cnt = 0;
			//proveri da li svi x mogu parni
			int ok1 = 1;  
			for (auto v : u.s) {
				if (v.s == '+')	
					ok1 &= (v.f % 2 == 0);
				else
					ok1 &= (v.f % 2 == 1);
			}
			cnt += ok1;
			ok1 = 1;
			for (auto v : u.s) {
				if (v.s == '+')
					ok1 &= (v.f % 2 == 1);
				else
					ok1 &= (v.f % 2 == 0);
			}
			cnt += ok1;
			g = mul(g, cnt);
			pr = u.f;
		}
		g = mul(binpow(2, n - pr), g);
		ans += g;
		pr = 0, g = 1;
		for (auto u : sv1) {
			int p = u.f - pr - 1;
			g = mul(g, binpow(2, p));
			int cnt = 0;
			//proveri da li svi x mogu parni
			int ok1 = 1;
			for (auto v : u.s) {
				if (v.s == '+')	
					ok1 &= (v.f % 2 == 0);
				else
					ok1 &= (v.f % 2 == 1);
			}
			cnt += ok1;
			ok1 = 1;
			for (auto v : u.s) {
				if (v.s == '+')
					ok1 &= (v.f % 2 == 1);
				else
					ok1 &= (v.f % 2 == 0);
			}
			cnt += ok1;
			g = mul(g, cnt);
			pr = u.f;
		}
		g = mul(binpow(2, m - pr), g);
		ans += g;
		int ok1 = 1;
		for (int i = 1;i <= k;i++) 
			ok1 &= ((x[i] + y[i]) % 2 == (c[i] == '-'));
		ans -= ok1;
		ok1 = 1;
		for (int i = 1;i <= k;i++)
			ok1 &= ((x[i] + y[i]) % 2 == (c[i] == '+'));
		ans -= ok1;
		cout << ans % mod;
  }
  return 0;
}

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