oj.uz

Submission #861412

# Submission time Handle Problem Language Result Execution time Memory
861412 2023-10-16T06:26:31 Z vjudge1 Crossing (JOI21_crossing) C++17
0 / 100
 103 ms 10376 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define F 
#define S second
#define endl '\n'
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
const int mod = 1e9 + 7, base = 13;
const int N =  1e6 + 15;
const ll inf = 1e18;
const int off = (1<<18);
vector<int> s[3];
int T[N];
char str[N];
int n, Q;
struct Sgt{
	#define ls (idx<<1)
	#define rs (idx<<1|1)
	struct data{
		int pws, val, tag;
		data() : pws(0), val(0), tag(-1) {}
	} t[off*2];
	void pull(int idx){
		t[idx].pws = t[ls].pws + t[rs].pws;
		t[idx].val = t[ls].val + t[rs].val;
		return;
	}
	void push(int idx){
		if (~t[idx].tag){
			t[idx].val = 1ll * t[idx].pws * t[idx].tag % mod;
			if (idx < off) t[ls].tag = t[rs].tag = t[idx].tag;
			t[idx].tag = ~0;
		}
		return;
	}
	void build(){
		for (int idx=off, p=1;idx<off*2;idx++, p=1ll*p*base%mod){
			t[idx].pws = p;
			t[idx].val = 1ll*p*T[idx-off] % mod;
			t[idx].tag = ~0;
		}
		for (int idx=off-1;idx>=1;idx--){
			t[idx].pws = t[ls].pws+t[rs].pws;
			t[idx].val = t[ls].val+t[rs].val;
			t[idx].tag = ~0;
		}
	}
	void update(int l, int r, int val, int idx=1, int lo=0, int hi=off){
		push(idx);
		if (r<=lo||hi<=l) return;
		if (l<=lo&&hi<=r){
			t[idx].tag = val;
			push(idx);
			return;
		}
		int mi = (lo+hi) >> 1;
		update(l, r, val, ls, lo, mi);
		update(l, r, val, rs, mi, hi);
		pull(idx);
	}
	#undef ls
	#undef rs
} seg;
int hsh(vector<int> cur){
	int res = 0;
	for (int i=0, p=1;i<n;i++, p=1ll*p*base % mod){
		res = (res + 1ll*cur[i]*p) % mod;
	}
	return res;
}
vector<int> cross(vector<int> lhs, vector<int> rhs){
	vector<int> cur(n);
	for (int i=0, p=1;i<n;i++, p = 1ll*p*base%mod){
		int c=0;
		if (lhs[i]==rhs[i]) c = lhs[i];
		else if (lhs[i]!=0&&rhs[i]!=0) c = 0;
		else if (lhs[i]!=1&&rhs[i]!=1) c = 1;
		else if (lhs[i]!=2&&rhs[i]!=2) c = 2;
		cur[i] = c;
	}
	return cur;
}
int32_t main(){
	cin >> n;
	for (int k=0;k<3;k++){
		scanf("%s", str);
		s[k].resize(n);
		for (int i=0;i<n;i++){
			if (str[i]=='J') s[k][i] = 0;
			if (str[i]=='O') s[k][i] = 1;
			if (str[i]=='I') s[k][i] = 2;
		}
	}
	set<int> st;
	st.insert(hsh(s[0]));
	st.insert(hsh(s[1]));
	st.insert(hsh(s[2]));
	st.insert(hsh(cross(s[0],s[1])));
	st.insert(hsh(cross(s[1],s[2])));
	st.insert(hsh(cross(s[0],s[2])));
	st.insert(hsh(cross(s[0],cross(s[1],s[2]))));
	st.insert(hsh(cross(s[1],cross(s[0],s[2]))));
	st.insert(hsh(cross(s[2],cross(s[0],s[1]))));
	scanf("%d", &Q);
	scanf("%s", str);
	for (int i=0;i<n;i++){
		if (str[i]=='J') T[i] = 0;
		if (str[i]=='O') T[i] = 1;
		if (str[i]=='I') T[i] = 2;
	}
	seg.build();
	if (st.find(seg.t[1].val)!=st.end()){
		puts("Yes");
	}
	else {
		puts("No");
	}
	while (Q--){
		int L, R;
		char C;
		scanf("%d %d %c", &L, &R, &C);
		int c=0;
		if (C=='J') c = 0;
		if (C=='O') c = 1;
		if (C=='I') c = 2;
		seg.update(L-1, R, c);
	     	int val = seg.t[1].val; 
		if (st.find(val)!=st.end()){
			puts("Yes");
		}
		else {
			puts("No");
		}
	}
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |   scanf("%s", str);
      |   ~~~~~^~~~~~~~~~~
Main.cpp:107:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:108:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |  scanf("%s", str);
      |  ~~~~~^~~~~~~~~~~
Main.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   scanf("%d %d %c", &L, &R, &C);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10376 KB Output is correct
2 Correct 103 ms 10192 KB Output is correct
3 Correct 102 ms 10324 KB Output is correct
4 Incorrect 89 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10376 KB Output is correct
2 Correct 103 ms 10192 KB Output is correct
3 Correct 102 ms 10324 KB Output is correct
4 Incorrect 89 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10376 KB Output is correct
2 Correct 103 ms 10192 KB Output is correct
3 Correct 102 ms 10324 KB Output is correct
4 Incorrect 89 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 10376 KB Output is correct
2 Correct 103 ms 10192 KB Output is correct
3 Correct 102 ms 10324 KB Output is correct
4 Incorrect 89 ms 10320 KB Output isn't correct
5 Halted 0 ms 0 KB -