oj.uz

Submission #670929

# Submission time Handle Problem Language Result Execution time Memory
670929 2022-12-11T10:45:21 Z Makarooni Plus Minus (BOI17_plusminus) C++14
100 / 100
 240 ms 36852 KB 
/* IN THE NAME OF GOD */
/* |\/| /-\ |\| | |\/| /-\ */

#include "bits/stdc++.h"
using namespace std;

#define sz(x) (int)x.size()
#define endl '\n'
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
#define mr make_pair
//#define int long long
#define pii pair<int, int>
typedef long double ld;
typedef long long ll;

mt19937 rng (chrono::high_resolution_clock::now().time_since_epoch().count());

const int N = 2e5 + 10;
const ll MOD = 1e9 + 7;
const int inf = 1e9;
const ll INF = 2e18;

vector<int> h[N][2], w[N][2];
vector<int> vx, vy;
int Q[N][3];

int pw(int a, int b){
	if(b == 0)
		return 1;
	int p = pw(a, b / 2);
	p = (1LL * p * p) % MOD;
	if(b % 2)
		p = (1LL * p * a) % MOD;
	return p;
}

int fx(int x){
	return lower_bound(all(vx), x) - vx.begin();
}

int fy(int y){
	return lower_bound(all(vy), y) - vy.begin();
}

int32_t main(){
	ios_base:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	char s;
	int x, y;
	set<int> X, Y;
	for(int i = 1; i <= q; i++){
		cin >> s >> x >> y;
		vx.pb(x);
		vy.pb(y);
		Q[i][0] = (s == '+');
		Q[i][1] = x;
		Q[i][2] = y;
	}
	sort(all(vx));
	sort(all(vy));
	vx.resize(unique(all(vx)) - vx.begin());
	vy.resize(unique(all(vy)) - vy.begin());
	int t;
	for(int i = 1; i <= q; i++){
		t = Q[i][0];
		x = Q[i][1];
		y = Q[i][2];
		h[fx(x)][y % 2].pb(t);
		w[fy(y)][x % 2].pb(t);
		X.insert(x);
		Y.insert(y);
	}
	bool f = 1;
	for(int i = 0; i <= 100000; i++){
		for(int j = 1; j < sz(h[i][0]); j++){
			if(h[i][0][j] != h[i][0][j - 1]){
				f = 0;
				break;
			}
		}
		if(!f)
			break;
		for(int j = 1; j < sz(h[i][1]); j++){
			if(h[i][1][j] != h[i][1][j - 1]){
				f = 0;
				break;
			}
		}
		if(!f)
			break;
		if(sz(h[i][0]) >= 1 && sz(h[i][1]) >= 1){
			if(h[i][0][0] == h[i][1][0]){
				f = 0;
				break;
			}
		}
	}
	bool f2 = 1;
	for(int i = 0; i <= 100000; i++){
		for(int j = 1; j < sz(w[i][0]); j++){
			if(w[i][0][j] != w[i][0][j - 1]){
				f2 = 0;
				break;
			}
		}
		if(!f2)
			break;
		for(int j = 1; j < sz(w[i][1]); j++){
			if(w[i][1][j] != w[i][1][j - 1]){
				f2 = 0;
				break;
			}
		}
		if(!f2)
			break;
		if(sz(w[i][0]) >= 1 && sz(w[i][1]) >= 1){
			if(w[i][0][0] == w[i][1][0]){
				f2 = 0;
				break;
			}
		}
	}
	//cout << n << " " << sz(X) << endl;
	ll ans = 0;
	if(f)
		ans = pw(2, n - sz(X));
	if(f2)
		ans += pw(2, m - sz(Y));
	ans %= MOD;
	if(f && f2)
		ans--;
	if(q == 0)
		ans--;
	if(ans < 0)
		ans += MOD;
	cout << ans;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19064 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 14 ms 19120 KB Output is correct
5 Correct 10 ms 19116 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct

Subtask #2
42.0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19064 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 14 ms 19120 KB Output is correct
5 Correct 10 ms 19116 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19248 KB Output is correct
12 Correct 10 ms 19120 KB Output is correct
13 Correct 10 ms 19120 KB Output is correct
14 Correct 13 ms 19156 KB Output is correct
15 Correct 11 ms 19256 KB Output is correct
16 Correct 64 ms 22580 KB Output is correct
17 Correct 62 ms 22588 KB Output is correct
18 Correct 70 ms 22704 KB Output is correct
19 Correct 63 ms 22620 KB Output is correct
20 Correct 62 ms 22584 KB Output is correct

Subtask #3
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 19028 KB Output is correct
2 Correct 12 ms 19064 KB Output is correct
3 Correct 10 ms 19028 KB Output is correct
4 Correct 14 ms 19120 KB Output is correct
5 Correct 10 ms 19116 KB Output is correct
6 Correct 11 ms 19028 KB Output is correct
7 Correct 12 ms 19028 KB Output is correct
8 Correct 10 ms 19028 KB Output is correct
9 Correct 10 ms 19028 KB Output is correct
10 Correct 10 ms 19028 KB Output is correct
11 Correct 11 ms 19248 KB Output is correct
12 Correct 10 ms 19120 KB Output is correct
13 Correct 10 ms 19120 KB Output is correct
14 Correct 13 ms 19156 KB Output is correct
15 Correct 11 ms 19256 KB Output is correct
16 Correct 64 ms 22580 KB Output is correct
17 Correct 62 ms 22588 KB Output is correct
18 Correct 70 ms 22704 KB Output is correct
19 Correct 63 ms 22620 KB Output is correct
20 Correct 62 ms 22584 KB Output is correct
21 Correct 175 ms 31500 KB Output is correct
22 Correct 12 ms 19056 KB Output is correct
23 Correct 183 ms 31552 KB Output is correct
24 Correct 193 ms 31516 KB Output is correct
25 Correct 174 ms 31520 KB Output is correct
26 Correct 182 ms 34028 KB Output is correct
27 Correct 183 ms 33940 KB Output is correct
28 Correct 187 ms 33920 KB Output is correct
29 Correct 182 ms 33952 KB Output is correct
30 Correct 240 ms 36852 KB Output is correct