oj.uz

Submission #902559

# Submission time Handle Problem Language Result Execution time Memory
902559 2024-01-10T17:37:38 Z qin Crossing (JOI21_crossing) C++17
26 / 100
 399 ms 43696 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ssize(x) int(x.size())
#define pn printf("\n")
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int inf = 2e09; ll infll = 2e18;
vector<string> get_strings(string &xx, string &y, string &z){
		string s[3] = {xx, y, z};
		int n = int(s[0].length());
		map<string, int> mp;
		queue<string> q;
		vector<string> ret;
		for(int l = 0; l < 3; ++l) mp[s[l]] = 1, q.emplace(s[l]), ret.emplace_back(s[l]);
		char t[3] = {'J', 'O', 'I'};
		int cnt = 0;
		while(!q.empty()){
				string x = q.front(); q.pop();
				string tt = ""; tt.resize(n);
				for(string &u : ret){
						for(int i = 0; i < n; ++i) if(x[i] == u[i]) tt[i] = x[i];
												   else{
														int a, b;
														for(int j = 0; j < 3; ++j) if(t[j] == x[i]) a = j;
														for(int j = 0; j < 3; ++j) if(t[j] == u[i]) b = j;
														if(a && b) tt[i] = t[0];
														else if(max(a, b) > 1) tt[i] = t[1];
														else tt[i] = t[2];
												   }
						if(mp[tt] != 1) mp[tt] = 1, q.emplace(tt), ++cnt, ret.emplace_back(tt);//, cout << ":\n" << x << "\n" << u << "\n" << tt << "\n\n";
				}
				//~ cout << x << "\n";
		}
		return ret;
}
int base = 1;
struct seg{
		vector<ll> t, p, tmp, powp;
		ll mod;
		void build(int i, int s, int e){
				for(int j = s; j <= e; ++j) tmp[i] += powp[j];
				int mid = (s+e)>>1;
				if(s != e) build(i<<1, s, mid), build(i<<1|1, mid+1, e);
		}
		void init(int n, ll m, string &s){
				while(base < n) base <<= 1;
				t.resize(base<<1, 0), tmp.resize(base<<1, 0), powp.resize(base+1), p.resize(base<<1, 0);
				mod = m;
				powp[0] = 1;
				for(int i = 1; i <= base; ++i) powp[i] = powp[i-1]*mod;
				build(1, 1, base);
				for(int i = 0; i < int(s.length()); ++i) t[i+base] = ll(s[i])*powp[i+1];
				for(int i = base-1; i; --i) t[i] = t[i<<1]+t[i<<1|1];
		}
		void add(int i, ll pr){ t[i] = tmp[i]*pr, p[i] = pr; }
		void push(int i){ if(p[i]) add(i<<1, p[i]), add(i<<1|1, p[i]), p[i] = 0; }
		void update(int i, int s, int e, int x, int y, ll pr){
				if(x <= s && e <= y) return void(add(i, pr));
				int mid = (s+e)>>1; push(i);
				if(x <= mid) update(i<<1, s, mid, x, y, pr);
				if(mid < y) update(i<<1|1, mid+1, e, x, y, pr);
				t[i] = t[i<<1]+t[i<<1|1];
		}
};
void answer(){
		int n, q; scanf("%d", &n);
		string s[3] = {"", "", ""}, t="";
		char c;
		for(int l = 0; l < 3; ++l){
				c = getchar_unlocked();
				for(int i = 0; i < n; ++i) c = getchar_unlocked(), s[l] += c;
		}
		scanf("%d\n", &q);
		for(int i = 0; i < n; ++i) c = getchar_unlocked(), t += c;
		vector<string> st = get_strings(s[0], s[1], s[2]);
		
		vector<ll> powp(n+1); powp[0] = 1;
		for(int i = 1; i <= n; ++i) powp[i] = powp[i-1]*97ll;
		vector<ll> powp1(n+1); powp1[0] = 1;
		for(int i = 1; i <= n; ++i) powp1[i] = powp1[i-1]*1000000007ll;
		
		unordered_map<ll, bool> mp9, mp10;
		for(string &u : st){
				ll hash = 0;
				for(int i = 0; i < n; ++i) hash += ll(u[i])*powp[i+1];
				mp9[hash] = 1;
				hash = 0;
				for(int i = 0; i < n; ++i) hash += ll(u[i])*powp1[i+1];
				mp10[hash] = 1;
				//~ printf("%lld\n", hash);
		}
		
		seg seg, seg2; seg.init(n+1, 97, t); seg2.init(n+1, 1000000007, t);
		printf(mp9[seg.t[1]] && mp10[seg2.t[1]] ? "Yes\n" : "No\n");
		//~ printf("%lld\n", seg.t[1]);
		
		for(++q; --q; ){
				int a, b; 
				scanf("%d%d %c", &a, &b, &c);
				seg.update(1, 1, base, a, b, ll(c));
				seg2.update(1, 1, base, a, b, ll(c));
				printf(mp9[seg.t[1]] && mp10[seg2.t[1]] ? "Yes\n" : "No\n");
				//~ printf("%lld\n", seg2.t[1]);
		}
}
int main(){
		int T = 1;
		//~ ios_base::sync_with_stdio(0); cin.tie(0);
		for(++T; --T; ) answer();
		return 0;
}

Compilation message

Main.cpp: In function 'void answer()':
Main.cpp:69:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   int n, q; scanf("%d", &n);
      |             ~~~~~^~~~~~~~~~
Main.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%d\n", &q);
      |   ~~~~~^~~~~~~~~~~~
Main.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |     scanf("%d%d %c", &a, &b, &c);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 6908 KB Output is correct
2 Correct 114 ms 7364 KB Output is correct
3 Correct 90 ms 3428 KB Output is correct
4 Correct 91 ms 7364 KB Output is correct
5 Correct 92 ms 7332 KB Output is correct
6 Correct 126 ms 6936 KB Output is correct
7 Correct 102 ms 7168 KB Output is correct
8 Correct 96 ms 7524 KB Output is correct
9 Correct 92 ms 7364 KB Output is correct
10 Correct 105 ms 10424 KB Output is correct
11 Correct 100 ms 7792 KB Output is correct
12 Correct 116 ms 10436 KB Output is correct
13 Correct 113 ms 7728 KB Output is correct
14 Correct 114 ms 10432 KB Output is correct
15 Correct 97 ms 7608 KB Output is correct
16 Correct 103 ms 10440 KB Output is correct
17 Correct 100 ms 7620 KB Output is correct
18 Correct 86 ms 2352 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 6908 KB Output is correct
2 Correct 114 ms 7364 KB Output is correct
3 Correct 90 ms 3428 KB Output is correct
4 Correct 91 ms 7364 KB Output is correct
5 Correct 92 ms 7332 KB Output is correct
6 Correct 126 ms 6936 KB Output is correct
7 Correct 102 ms 7168 KB Output is correct
8 Correct 96 ms 7524 KB Output is correct
9 Correct 92 ms 7364 KB Output is correct
10 Correct 105 ms 10424 KB Output is correct
11 Correct 100 ms 7792 KB Output is correct
12 Correct 116 ms 10436 KB Output is correct
13 Correct 113 ms 7728 KB Output is correct
14 Correct 114 ms 10432 KB Output is correct
15 Correct 97 ms 7608 KB Output is correct
16 Correct 103 ms 10440 KB Output is correct
17 Correct 100 ms 7620 KB Output is correct
18 Correct 86 ms 2352 KB Output is correct
19 Correct 379 ms 40492 KB Output is correct
20 Correct 280 ms 40664 KB Output is correct
21 Correct 320 ms 43696 KB Output is correct
22 Correct 260 ms 39556 KB Output is correct
23 Correct 169 ms 12292 KB Output is correct
24 Correct 166 ms 12412 KB Output is correct
25 Correct 318 ms 43592 KB Output is correct
26 Correct 291 ms 40536 KB Output is correct
27 Correct 282 ms 43580 KB Output is correct
28 Correct 399 ms 40592 KB Output is correct
29 Correct 254 ms 43444 KB Output is correct
30 Correct 192 ms 12420 KB Output is correct
31 Correct 334 ms 43632 KB Output is correct
32 Correct 330 ms 40064 KB Output is correct
33 Correct 153 ms 12484 KB Output is correct
34 Correct 317 ms 40664 KB Output is correct
35 Correct 257 ms 39440 KB Output is correct
36 Correct 169 ms 12484 KB Output is correct
37 Correct 161 ms 12568 KB Output is correct
38 Correct 260 ms 39552 KB Output is correct
39 Correct 146 ms 38804 KB Output is correct
40 Incorrect 314 ms 39416 KB Output isn't correct
41 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 6908 KB Output is correct
2 Correct 114 ms 7364 KB Output is correct
3 Correct 90 ms 3428 KB Output is correct
4 Correct 91 ms 7364 KB Output is correct
5 Correct 92 ms 7332 KB Output is correct
6 Correct 126 ms 6936 KB Output is correct
7 Correct 102 ms 7168 KB Output is correct
8 Correct 96 ms 7524 KB Output is correct
9 Correct 92 ms 7364 KB Output is correct
10 Correct 105 ms 10424 KB Output is correct
11 Correct 100 ms 7792 KB Output is correct
12 Correct 116 ms 10436 KB Output is correct
13 Correct 113 ms 7728 KB Output is correct
14 Correct 114 ms 10432 KB Output is correct
15 Correct 97 ms 7608 KB Output is correct
16 Correct 103 ms 10440 KB Output is correct
17 Correct 100 ms 7620 KB Output is correct
18 Correct 86 ms 2352 KB Output is correct
19 Correct 99 ms 7112 KB Output is correct
20 Correct 95 ms 3392 KB Output is correct
21 Correct 111 ms 10408 KB Output is correct
22 Correct 84 ms 6776 KB Output is correct
23 Correct 151 ms 10344 KB Output is correct
24 Correct 88 ms 7108 KB Output is correct
25 Correct 103 ms 10404 KB Output is correct
26 Correct 109 ms 7088 KB Output is correct
27 Correct 103 ms 10324 KB Output is correct
28 Correct 92 ms 7104 KB Output is correct
29 Correct 101 ms 7432 KB Output is correct
30 Correct 113 ms 7032 KB Output is correct
31 Correct 107 ms 10436 KB Output is correct
32 Correct 113 ms 10468 KB Output is correct
33 Correct 92 ms 7616 KB Output is correct
34 Correct 94 ms 7108 KB Output is correct
35 Correct 106 ms 10432 KB Output is correct
36 Correct 103 ms 7616 KB Output is correct
37 Correct 98 ms 10432 KB Output is correct
38 Correct 115 ms 7724 KB Output is correct
39 Correct 120 ms 10444 KB Output is correct
40 Correct 93 ms 7604 KB Output is correct
41 Correct 97 ms 10436 KB Output is correct
42 Correct 100 ms 7620 KB Output is correct
43 Correct 102 ms 7224 KB Output is correct
44 Correct 97 ms 7620 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 6908 KB Output is correct
2 Correct 114 ms 7364 KB Output is correct
3 Correct 90 ms 3428 KB Output is correct
4 Correct 91 ms 7364 KB Output is correct
5 Correct 92 ms 7332 KB Output is correct
6 Correct 126 ms 6936 KB Output is correct
7 Correct 102 ms 7168 KB Output is correct
8 Correct 96 ms 7524 KB Output is correct
9 Correct 92 ms 7364 KB Output is correct
10 Correct 105 ms 10424 KB Output is correct
11 Correct 100 ms 7792 KB Output is correct
12 Correct 116 ms 10436 KB Output is correct
13 Correct 113 ms 7728 KB Output is correct
14 Correct 114 ms 10432 KB Output is correct
15 Correct 97 ms 7608 KB Output is correct
16 Correct 103 ms 10440 KB Output is correct
17 Correct 100 ms 7620 KB Output is correct
18 Correct 86 ms 2352 KB Output is correct
19 Correct 379 ms 40492 KB Output is correct
20 Correct 280 ms 40664 KB Output is correct
21 Correct 320 ms 43696 KB Output is correct
22 Correct 260 ms 39556 KB Output is correct
23 Correct 169 ms 12292 KB Output is correct
24 Correct 166 ms 12412 KB Output is correct
25 Correct 318 ms 43592 KB Output is correct
26 Correct 291 ms 40536 KB Output is correct
27 Correct 282 ms 43580 KB Output is correct
28 Correct 399 ms 40592 KB Output is correct
29 Correct 254 ms 43444 KB Output is correct
30 Correct 192 ms 12420 KB Output is correct
31 Correct 334 ms 43632 KB Output is correct
32 Correct 330 ms 40064 KB Output is correct
33 Correct 153 ms 12484 KB Output is correct
34 Correct 317 ms 40664 KB Output is correct
35 Correct 257 ms 39440 KB Output is correct
36 Correct 169 ms 12484 KB Output is correct
37 Correct 161 ms 12568 KB Output is correct
38 Correct 260 ms 39552 KB Output is correct
39 Correct 146 ms 38804 KB Output is correct
40 Incorrect 314 ms 39416 KB Output isn't correct
41 Halted 0 ms 0 KB -