oj.uz

Submission #894088

# Submission time Handle Problem Language Result Execution time Memory
894088 2023-12-28T00:51:24 Z OAleksa Plus Minus (BOI17_plusminus) C++14
100 / 100
 201 ms 25936 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 30 ms 7772 KB Output is correct
17 Correct 31 ms 7652 KB Output is correct
18 Correct 31 ms 7588 KB Output is correct
19 Correct 29 ms 7760 KB Output is correct
20 Correct 38 ms 7708 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 468 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 600 KB Output is correct
16 Correct 30 ms 7772 KB Output is correct
17 Correct 31 ms 7652 KB Output is correct
18 Correct 31 ms 7588 KB Output is correct
19 Correct 29 ms 7760 KB Output is correct
20 Correct 38 ms 7708 KB Output is correct
21 Correct 141 ms 18044 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 93 ms 17960 KB Output is correct
24 Correct 115 ms 17996 KB Output is correct
25 Correct 124 ms 18064 KB Output is correct
26 Correct 133 ms 21724 KB Output is correct
27 Correct 110 ms 21900 KB Output is correct
28 Correct 134 ms 21840 KB Output is correct
29 Correct 124 ms 21924 KB Output is correct
30 Correct 201 ms 25936 KB Output is correct