제출 #742653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
742653		ToniB	Crossing (JOI21_crossing)	C++17	100 / 100	5188 ms	24932 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 2;
const int OFF = 1 << 19;

const char let[] = {'J', 'O', 'I'};
inline int g(char& c){
	for(int i = 0; i < 3; ++i) if(let[i] == c) return i;
}

int n, q;
bool ans[MAXN];
struct Change {
	int l, r;
	char c;
} a[MAXN];
string poc[3];
string t;

struct Node{
	int cnt[3][2];
	int equal = 0;
	int prop = -1;
} tour[OFF];

Node merge(Node& a, Node& b){
	Node ret;
	for(int i = 0; i < 3; ++i){
		for(int j = 0; j < 2; ++j){
			ret.cnt[i][j] = a.cnt[i][j] + b.cnt[i][j];
		}
	}
	ret.equal = a.equal + b.equal;
	ret.prop = -1;
	return ret;
}
void propaj(int x, int l, int r){
	for(int i = 0; i < 3; ++i) tour[x].cnt[i][0] = 0;
	tour[x].cnt[tour[x].prop][0] = r - l + 1;
	tour[x].equal = tour[x].cnt[tour[x].prop][1];
	if(l != r){
		tour[x * 2 + 1].prop = tour[x].prop;
		tour[x * 2 + 2].prop = tour[x].prop;
	}
	tour[x].prop = -1;
}

void con(int x, int l, int r, string& s, bool t){
	tour[x].prop = -1;
	if(l == r){
		for(int i = 0; i < 3; ++i) tour[x].cnt[i][t] = 0;
		tour[x].cnt[g(s[l])][t] = 1;
		tour[x].equal = tour[x].cnt[g(s[l])][!t];
		return ;
	}
	int mid = (l + r) >> 1;
	con(x * 2 + 1, l, mid, s, t);
	con(x * 2 + 2, mid + 1, r, s, t);
	tour[x] = merge(tour[x * 2 + 1], tour[x * 2 + 2]);
}
void upd(int x, int l, int r, int ql, int qr, int val){
	if(tour[x].prop != -1) propaj(x, l, r);
	if(ql > r || l > qr) return ;
	if(ql <= l && r <= qr){
		tour[x].prop = val;
		propaj(x, l, r);
		return ;
	}
	int mid = (l + r) >> 1;
	upd(x * 2 + 1, l, mid, ql, qr, val);
	upd(x * 2 + 2, mid + 1, r, ql, qr, val);
	tour[x] = merge(tour[x * 2 + 1], tour[x * 2 + 2]);
}

string comp(string& a, string& b){
	string ret = "";
	for(int i = 0; i < n; ++i){
		if(a[i] == b[i]) ret += a[i];
		else for(char c : {'J', 'O', 'I'}){
			if(c != a[i] && c != b[i]) ret += c;
		}
	}
	return ret;
}

void solve(string s){
	con(0, 0, n - 1, s, 1);
	con(0, 0, n - 1, t, 0);
	ans[0] |= (tour[0].equal == n);
	for(int i = 1; i <= q; ++i){
		upd(0, 0, n - 1, a[i].l, a[i].r, g(a[i].c));
		ans[i] |= (tour[0].equal == n);
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);

	cin >> n;
	for(int i = 0; i < 3; ++i) cin >> poc[i];
	cin >> q >> t;
	for(int i = 1; i <= q; ++i){
		cin >> a[i].l >> a[i].r >> a[i].c;
		--a[i].l, --a[i].r;
	}
	for(int i = 1; i < 8; ++i){
		string cur = "";
		vector<int> tmp;
		for(int j = 0; j < 3; ++j){
			if(i & 1 << j) tmp.push_back(j);
		}
		do{
			cur = poc[tmp[0]];
			for(int j = 1; j < (int)tmp.size(); ++j) cur = comp(cur, poc[tmp[j]]);
			solve(cur);
		} while(next_permutation(tmp.begin(), tmp.end()));
	}
	for(int i = 0; i <= q; ++i){
		if(ans[i]) cout << "Yes\n";
		else cout << "No\n";
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int g(char&)':
Main.cpp:9:1: warning: control reaches end of non-void function [-Wreturn-type]
    9 | }
      | ^

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51