Submission #479389

#	Time	Username	Problem	Language	Result	Execution time	Memory
479389		Arvin	Crossing (JOI21_crossing)	C++11	26 / 100	7084 ms	10340 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ull unsigned long long
#define ll long long
#define ui unsigned int
#define us unsigned short
#define inf_int 1e9
#define inf_ll 1e18
#define mod 1000000007
#define smod 998244353

map<pair<char, char>, char> mp;

const int maxN = 2e5 + 5;
const ll base = 5;

int n;
ll prefix[maxN];

ll convert(char c){
	if(c == 'J') return 0;
	else if(c == 'O') return 1;
	else if(c == 'I') return 2;
}

struct SegTree { // index start from 0 (v)
	ll tree[4*maxN], lazy[4*maxN];
	
	int n;
	void resize(int m){
		n = m;
	}
	
	void build(int v, int l, int r, string s){
		if(l > r) return;
		if(l == r){
			tree[v] = (prefix[l] - (l > 0 ? prefix[l-1] : 0) + mod) % mod * convert(s[l]) % mod;
			lazy[v] = -1;
			return;
		}
		
		int m = (l+r) >> 1;
		build(v*2+1, l, m, s);
		build(v*2+2, m+1, r, s);
		
		tree[v] = (tree[v*2+1] + tree[v*2+2]) % mod;
		lazy[v] = -1;
	}
	
	void push(int v, int l, int m, int r){
		if(lazy[v] == -1) return;
		
		tree[v*2+1] = (prefix[m] - (l > 0 ? prefix[l-1] : 0) + mod) % mod * lazy[v] % mod;
		lazy[v*2+1] = lazy[v];
		
		tree[v*2+2] = (prefix[r] - prefix[m] + mod) % mod * lazy[v] % mod;
		lazy[v*2+2] = lazy[v];
		
		lazy[v] = -1;
	}
	
	void update(int v, int curL, int curR, int l, int r, ll val){
		if(l > r) return;
		if(curL == l && r == curR){
			tree[v] = (prefix[curR] - (curL > 0 ? prefix[curL-1] : 0) + mod) % mod * val % mod;
			lazy[v] = val;
		} else {
			int curM = (curL+curR) >> 1;
			
			push(v, curL, curM, curR);
			
			update(v*2+1, curL, curM, l, min(r, curM), val);
			update(v*2+2, curM+1, curR, max(l, curM+1), r, val);
			
			tree[v] = (tree[v*2+1] + tree[v*2+2]) % mod;
		}
	}
	
	ll query(int v, int curL, int curR, int l, int r){
		if(l > r || curL > curR) return 0;
		if(l <= curL && curR <= r){
			return tree[v];
		}
		
		int curM = (curL+curR) >> 1;

		push(v, curL, curM, curR);
		
		return (query(v*2+1, curL, curM, l, min(r, curM)) + query(v*2+2, curM+1, curR, max(l, curM+1), r)) % mod;
	}
};

SegTree tree;

int main(){
	ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	
	mp[{'J', 'O'}] = mp[{'O', 'J'}] = 'I';
	mp[{'J', 'I'}] = mp[{'I', 'J'}] = 'O';
	mp[{'I', 'O'}] = mp[{'O', 'I'}] = 'J';
	
	cin >> n;
	
	ll cur = 1;
	prefix[0] = 1;
	for(int x=1;x<n;x++){
		cur *= base;
		cur %= mod;
		prefix[x] = (prefix[x-1] + cur) % mod;
	}
	
	set<string> st;
	vector<string> v;
	
	for(int x=0;x<3;x++){
		string s;
		cin >> s;
		
		if(!st.count(s)){
			st.insert(s);
			v.push_back(s);
		}
	}
	
	for(int x=0;x<v.size();x++){
		for(int y=0;y<x;y++){
			string tmp;
			for(int z=0;z<v[x].length();z++){
				if(v[x][z] == v[y][z]){
					tmp.push_back(v[x][z]);
				} else {
					tmp.push_back(mp[{v[x][z], v[y][z]}]);
				}
			}
			
			if(!st.count(tmp)){
				st.insert(tmp);
				v.push_back(tmp);
			}
		}
	}
	
	set<ll> st2;
	for(auto s : st){
		ll val = 0, cur = 1;
		for(int x=0;x<n;x++){
			val += convert(s[x]) * cur % mod;
			val %= mod;
			cur *= base;
			cur %= mod;
		}	
		
		st2.insert(val);
	}
	
	int q;
	cin >> q;
	
	string t;
	cin >> t;
	
	tree.resize(n);
	tree.build(0, 0, n-1, t);
	
	if(st2.count(tree.query(0, 0, n-1, 0, n-1))){
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
	
	for(int i=1;i<=q;i++){
		int l, r;
		char c;
		cin >> l >> r >> c;
		
		l--; r--;
		tree.update(0, 0, n-1, l, r, convert(c));
		
		if(st2.count(tree.query(0, 0, n-1, 0, n-1))){
			cout << "Yes\n";
		} else {
			cout << "No\n";
		}
	}
	
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:129:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |  for(int x=0;x<v.size();x++){
      |              ~^~~~~~~~~
Main.cpp:132:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |    for(int z=0;z<v[x].length();z++){
      |                ~^~~~~~~~~~~~~~
Main.cpp: In function 'long long int convert(char)':
Main.cpp:26:1: warning: control reaches end of non-void function [-Wreturn-type]
   26 | }
      | ^

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