oj.uz

Submission #420364

# Submission time Handle Problem Language Result Execution time Memory
420364 2021-06-08T10:11:18 Z InternetPerson10 Crossing (JOI21_crossing) C++17
0 / 100
 636 ms 22248 KB 
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const ll MOD = 1000000007;

vector<int> nums[3];
vector<int> anss[9];
vector<int> tar;
vector<pair<pair<int, int>, int>> qs;
bool good[300001];
ll pow3[300001][4], sum3[300001][4];
ll ha[9][4];
vector<ll> ps = {1000000007, 1000000009, 1000000021, 1000000033};

vector<int> combine(vector<int> v1, vector<int> v2) {
	vector<int> v;
	v.resize(v1.size());
	for(int i = 0; i < v.size(); i++) v[i] = (6 - v1[i] - v2[i])%3;
	return v;
}

struct segTree {
	ll prime; int typ;
	vector<ll> nums, ops;
	int size = 1;
	void init(int n, ll p, int t) {
		while(size < n) size *= 2;
		vector<ll>().swap(nums);
		nums.resize(2*size, 0);
		ops.resize(2*size, -1);
		prime = p;
		typ = t;
	}
	void prop(int n, int d) {
		if(ops[n] == -1) return;
		if(n >= size) {
			nums[n] = ops[n];
			ops[n] = -1;
			return;
		}
		prop(2*n+1, d);
		prop(2*n+2, d);
		ops[2*n+1] = ops[n];
		ops[2*n+2] = ops[n];
		nums[n] = (ops[n] * sum3[d-1][typ])%prime;
		ops[n] = -1;
		return;
	}
	void set(int l, int r, int v, int n, int lx, int rx) {
		prop(n, rx - lx);
		if(l >= rx || lx >= r) return;
		if(l <= lx && rx <= r) {
			ops[n] = v;
			nums[n] = (ops[n] * sum3[rx-lx-1][typ])%prime;
			return;
		}
		int mid = (lx + rx)/2;
		set(l, r, v, 2*n+1, lx, mid);
		set(l, r, v, 2*n+2, mid, rx);
		nums[n] = (pow3[mid - lx][typ] * nums[2*n+1] + nums[2*n+2])%prime;
		return;
	}
	void set(int l, int r, int v) {
		set(l, r, v, 0, 0, size);
	}
	ll get() {
		prop(0, size);
		return nums[0];
	}
};

segTree st[4];

int getChar(char c) {
	if(c == 'J') return 0;
	if(c == 'O') return 1;
	return 2;
}

bool check() {
	for(int i = 0; i < 9; i++) {
		bool sad = false;
		for(int z = 0; z < 2; z++) {
			if(st[z].get() != ha[i][z]) sad = true;
			// cout << st[z].get() << ' ';
		}
		// cout << '\n';
		if(!sad) return true;
	}
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	ll k = 1;
	for(int z = 0; z < 2; z++) {
		k = 1;
		for(int i = 0; i <= 300000; i++) {
			pow3[i][z] = k;
			k *= 3;
			if(k > ps[z]) k %= ps[z];
			if(i == 0) sum3[i][z] = pow3[i][z];
			else sum3[i][z] = (sum3[i-1][z] + pow3[i][z])%ps[z];
		}
	}
	int n, q;
	int size = 1;
	string s;
	cin >> n;
	while(size < n) {
		size *= 2;
	}
	for(int i = 0; i < 3; i++) {
		cin >> s;
		nums[i].resize(n);
		for(int j = 0; j < n; j++) {
			if(s.at(j) == 'J') nums[i][j] = 0;
			else if(s.at(j) == 'O') nums[i][j] = 1;
			else nums[i][j] = 2;
		}
		anss[i] = nums[i];
	}
	anss[3] = combine(nums[0], nums[1]);
	anss[4] = combine(nums[1], nums[2]);
	anss[5] = combine(nums[0], nums[2]);
	anss[6] = combine(anss[3], nums[2]);
	anss[7] = combine(anss[4], nums[0]);
	anss[8] = combine(anss[5], nums[1]);
	for(int z = 0; z < 2; z++) {
		for(int i = 0; i < 9; i++) {
			ll k = 0;
			for(int j = 0; j < size; j++) {
				k *= 3;
				if(j < anss[i].size()) k += anss[i][j];
				k %= ps[z];
			}
			ha[i][z] = k;
			// cout << ha[i][z] << ' ';
		}
		// cout << '\n';
	}
	cin >> q >> s;
	tar.resize(n);
	qs.resize(q);
	for(int z = 0; z < 2; z++) {
		st[z].init(n, ps[z], z);
	}
	for(int z = 0; z < 2; z++) {
		for(int i = 0; i < n; i++) {
			st[z].set(i, i+1, getChar(s.at(i)));
		}
	}
	good[0] = check();
	for(int i = 0; i < q; i++) {
		int x, y;
		char c;
		cin >> x >> y >> c;
		int z;
		if(c == 'J') z = 0;
		else if(c == 'O') z = 1;
		else z = 2;
		for(int m = 0; m < 2; m++) st[m].set(x-1, y, z);
		good[i+1] = check();
	}
	for(int i = 0; i <= q; i++) {
		if(good[i]) cout << "Yes\n";
		else cout << "No\n";
	}
}

Compilation message

Main.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
Main.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int i = 0; i < v.size(); i++) v[i] = (6 - v1[i] - v2[i])%3;
      |                 ~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:137:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |     if(j < anss[i].size()) k += anss[i][j];
      |        ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 21996 KB Output is correct
2 Correct 279 ms 22248 KB Output is correct
3 Correct 636 ms 22176 KB Output is correct
4 Correct 226 ms 22084 KB Output is correct
5 Correct 239 ms 22056 KB Output is correct
6 Correct 233 ms 22084 KB Output is correct
7 Correct 213 ms 22208 KB Output is correct
8 Correct 238 ms 22144 KB Output is correct
9 Correct 228 ms 22244 KB Output is correct
10 Incorrect 242 ms 22212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 21996 KB Output is correct
2 Correct 279 ms 22248 KB Output is correct
3 Correct 636 ms 22176 KB Output is correct
4 Correct 226 ms 22084 KB Output is correct
5 Correct 239 ms 22056 KB Output is correct
6 Correct 233 ms 22084 KB Output is correct
7 Correct 213 ms 22208 KB Output is correct
8 Correct 238 ms 22144 KB Output is correct
9 Correct 228 ms 22244 KB Output is correct
10 Incorrect 242 ms 22212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 21996 KB Output is correct
2 Correct 279 ms 22248 KB Output is correct
3 Correct 636 ms 22176 KB Output is correct
4 Correct 226 ms 22084 KB Output is correct
5 Correct 239 ms 22056 KB Output is correct
6 Correct 233 ms 22084 KB Output is correct
7 Correct 213 ms 22208 KB Output is correct
8 Correct 238 ms 22144 KB Output is correct
9 Correct 228 ms 22244 KB Output is correct
10 Incorrect 242 ms 22212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 21996 KB Output is correct
2 Correct 279 ms 22248 KB Output is correct
3 Correct 636 ms 22176 KB Output is correct
4 Correct 226 ms 22084 KB Output is correct
5 Correct 239 ms 22056 KB Output is correct
6 Correct 233 ms 22084 KB Output is correct
7 Correct 213 ms 22208 KB Output is correct
8 Correct 238 ms 22144 KB Output is correct
9 Correct 228 ms 22244 KB Output is correct
10 Incorrect 242 ms 22212 KB Output isn't correct
11 Halted 0 ms 0 KB -