oj.uz

Submission #423432

# Submission time Handle Problem Language Result Execution time Memory
423432 2021-06-11T06:01:54 Z 송준혁(#7517) Crossing (JOI21_crossing) C++17
0 / 100
 114 ms 4036 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define MOD 1000000007
#define INF (1ll<<62)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

int N, Q;
int A[202020][10], S[202020];
int X[808080][10], lz[808080];
bool T[808080][10];

void init(int id, int s, int e){
	if (s == e){
		for (int i=0; i<9; i++) X[id][i] = A[s][i];
		for (int i=0; i<9; i++) if (X[id][i] == S[s]) T[id][i] = true;
		return;
	}
	int m=s+e>>1;
	init(id*2, s, m), init(id*2+1, m+1, e);
	for (int i=0; i<9; i++){
		T[id][i] = T[id*2][i] && T[id*2+1][i];
		if (X[id*2][i] == X[id*2+1][i]) X[id][i] = X[id*2][i];
		else X[id][i] = -1;
	}
}

void busy(int id){
	if (lz[id] < 0) return;
	for (int i=0; i<9; i++){
		T[id*2][i] = (X[id*2][i] == lz[id]);
		T[id*2+1][i] = (X[id*2+1][i] == lz[id]);
	}
	lz[id*2] = lz[id*2+1] = lz[id];
	lz[id] = -1;
}

void upd(int id, int s, int e, int ts, int te, int v){
	if (e < ts || te < s) return;
	if (ts <= s && e <= te){
		for (int i=0; i<9; i++) T[id][i] = (X[id][i] == v);
		lz[id] = v;
		return;
	}
	busy(id);
	int m=s+e>>1;
	upd(id*2, s, m, ts, te, v);
	upd(id*2+1, m+1, e, ts, te, v);
	for (int i=0; i<9; i++) T[id][i] = T[id*2][i] && T[id*2+1][i];
}

int main(){
	char ch;
	scanf("%d", &N);
	for (int i=1; i<=N; i++){
		scanf(" %c", &ch);
		if (ch == 'J') A[i][0] = 0;
		if (ch == 'O') A[i][0] = 1;
		if (ch == 'I') A[i][0] = 2;
	}
	for (int i=1; i<=N; i++){
		scanf(" %c", &ch);
		if (ch == 'J') A[i][1] = 0;
		if (ch == 'O') A[i][1] = 1;
		if (ch == 'I') A[i][1] = 2;
	}
	for (int i=1; i<=N; i++){
		scanf(" %c", &ch);
		if (ch == 'J') A[i][2] = 0;
		if (ch == 'O') A[i][2] = 1;
		if (ch == 'I') A[i][2] = 2;
	}
	for (int i=1; i<=N; i++) A[i][3] = (2*A[i][0] + 1*A[i][1] + 1*A[i][2])%3;
	for (int i=1; i<=N; i++) A[i][4] = (1*A[i][0] + 2*A[i][1] + 1*A[i][2])%3;
	for (int i=1; i<=N; i++) A[i][5] = (1*A[i][0] + 1*A[i][1] + 2*A[i][2])%3;
	for (int i=1; i<=N; i++) A[i][6] = (0*A[i][0] + 2*A[i][1] + 2*A[i][2])%3;
	for (int i=1; i<=N; i++) A[i][7] = (2*A[i][0] + 0*A[i][1] + 2*A[i][2])%3;
	for (int i=1; i<=N; i++) A[i][8] = (2*A[i][0] + 2*A[i][1] + 0*A[i][2])%3;
	scanf("%d", &Q);
	for (int i=1; i<=N; i++){
		scanf(" %c", &ch);
		if (ch == 'J') S[i] = 0;
		if (ch == 'O') S[i] = 1;
		if (ch == 'I') S[i] = 2;
	}
	memset(lz, -1, sizeof lz);
	init(1, 1, N);
	bool tf=false;
	for (int i=0; i<9; i++) tf = tf || T[1][i];
	puts(tf?"YES":"NO");
	while (Q--){
		int l, r, v;
		scanf("%d %d %c", &l, &r, &ch);
		if (ch == 'J') v = 0;
		if (ch == 'O') v = 1;
		if (ch == 'I') v = 2;
		upd(1, 1, N, l, r, v);
		tf = false;
		for (int i=0; i<9; i++) tf = tf || T[1][i];
		puts(tf?"YES":"NO");
	}
	return 0;
}

Compilation message

Main.cpp: In function 'void init(int, int, int)':
Main.cpp:23:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   23 |  int m=s+e>>1;
      |        ~^~
Main.cpp: In function 'void upd(int, int, int, int, int, int)':
Main.cpp:50:9: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int m=s+e>>1;
      |        ~^~
Main.cpp: In function 'int main()':
Main.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Main.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf(" %c", &ch);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf(" %c", &ch);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf(" %c", &ch);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
Main.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf(" %c", &ch);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   scanf("%d %d %c", &l, &r, &ch);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:96:13: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   96 |   int l, r, v;
      |             ^

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 114 ms 4036 KB Output isn't correct
2 Halted 0 ms 0 KB -