oj.uz

Submission #915624

# Submission time Handle Problem Language Result Execution time Memory
915624 2024-01-24T11:30:04 Z qin Crossing (JOI21_crossing) C++17
26 / 100
 686 ms 63120 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 unsigned 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;
    		ll r[256]; 
    		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){
    				r['J'] = 328336787, r['O'] = 760308421, r['I'] = 988411051;
    				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] = r[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;
    		vector<ll> powp2(n+1); powp2[0] = 1;
    		for(int i = 1; i <= n; ++i) powp2[i] = powp2[i-1]*2137ll;
    		
    		ll r[256]; r['J'] = 328336787, r['O'] = 760308421, r['I'] = 988411051;
    		unordered_map<ll, bool> mp9, mp10, mp11;
    		for(string &u : st){
    				ll hash = 0;
    				for(int i = 0; i < n; ++i) hash += r[u[i]]*powp[i+1];
    				mp9[hash] = 1;
    				hash = 0;
    				for(int i = 0; i < n; ++i) hash += r[u[i]]*powp1[i+1];
    				mp10[hash] = 1;
    				hash = 0;
    				for(int i = 0; i < n; ++i) hash += r[u[i]]*powp2[i+1];
    				mp11[hash] = 1;
    				//~ printf("%lld\n", hash);
    		}
    		
    		seg seg, seg2, seg3; seg.init(n+1, 97, t); seg2.init(n+1, 1000000007, t), seg3.init(n+1, 2137, t);
    		printf(mp9[seg.t[1]] && mp10[seg2.t[1]] && mp11[seg3.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, r[c]);
    				seg2.update(1, 1, base, a, b, r[c]);
    				seg3.update(1, 1, base, a, b, r[c]);
    				printf(mp9[seg.t[1]] && mp10[seg2.t[1]] && mp11[seg3.t[1]] ? "Yes\n" : "No\n");
    				//~ printf("%lld\n", seg3.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 member function 'void seg::init(int, ll, std::string&)':
Main.cpp:56:68: warning: array subscript has type 'char' [-Wchar-subscripts]
   56 |         for(int i = 0; i < int(s.length()); ++i) t[i+base] = r[s[i]]*powp[i+1];
      |                                                                    ^
Main.cpp: In function 'void answer()':
Main.cpp:92:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   92 |         for(int i = 0; i < n; ++i) hash += r[u[i]]*powp[i+1];
      |                                                  ^
Main.cpp:95:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   95 |         for(int i = 0; i < n; ++i) hash += r[u[i]]*powp1[i+1];
      |                                                  ^
Main.cpp:98:50: warning: array subscript has type 'char' [-Wchar-subscripts]
   98 |         for(int i = 0; i < n; ++i) hash += r[u[i]]*powp2[i+1];
      |                                                  ^
Main.cpp:109:40: warning: array subscript has type 'char' [-Wchar-subscripts]
  109 |         seg.update(1, 1, base, a, b, r[c]);
      |                                        ^
Main.cpp:110:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  110 |         seg2.update(1, 1, base, a, b, r[c]);
      |                                         ^
Main.cpp:111:41: warning: array subscript has type 'char' [-Wchar-subscripts]
  111 |         seg3.update(1, 1, base, a, b, r[c]);
      |                                         ^
Main.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |       int n, q; scanf("%d", &n);
      |                 ~~~~~^~~~~~~~~~
Main.cpp:77:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |       scanf("%d\n", &q);
      |       ~~~~~^~~~~~~~~~~~
Main.cpp:108:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         scanf("%d%d %c", &a, &b, &c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 8388 KB Output is correct
2 Correct 129 ms 8900 KB Output is correct
3 Correct 112 ms 4960 KB Output is correct
4 Correct 106 ms 8920 KB Output is correct
5 Correct 107 ms 8900 KB Output is correct
6 Correct 116 ms 8568 KB Output is correct
7 Correct 115 ms 8608 KB Output is correct
8 Correct 110 ms 9140 KB Output is correct
9 Correct 116 ms 8916 KB Output is correct
10 Correct 117 ms 12052 KB Output is correct
11 Correct 113 ms 9292 KB Output is correct
12 Correct 119 ms 12008 KB Output is correct
13 Correct 121 ms 9612 KB Output is correct
14 Correct 116 ms 11972 KB Output is correct
15 Correct 113 ms 9196 KB Output is correct
16 Correct 120 ms 12044 KB Output is correct
17 Correct 122 ms 9292 KB Output is correct
18 Correct 102 ms 3756 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 8388 KB Output is correct
2 Correct 129 ms 8900 KB Output is correct
3 Correct 112 ms 4960 KB Output is correct
4 Correct 106 ms 8920 KB Output is correct
5 Correct 107 ms 8900 KB Output is correct
6 Correct 116 ms 8568 KB Output is correct
7 Correct 115 ms 8608 KB Output is correct
8 Correct 110 ms 9140 KB Output is correct
9 Correct 116 ms 8916 KB Output is correct
10 Correct 117 ms 12052 KB Output is correct
11 Correct 113 ms 9292 KB Output is correct
12 Correct 119 ms 12008 KB Output is correct
13 Correct 121 ms 9612 KB Output is correct
14 Correct 116 ms 11972 KB Output is correct
15 Correct 113 ms 9196 KB Output is correct
16 Correct 120 ms 12044 KB Output is correct
17 Correct 122 ms 9292 KB Output is correct
18 Correct 102 ms 3756 KB Output is correct
19 Correct 686 ms 60276 KB Output is correct
20 Correct 476 ms 60292 KB Output is correct
21 Correct 458 ms 62592 KB Output is correct
22 Correct 420 ms 58628 KB Output is correct
23 Correct 192 ms 15812 KB Output is correct
24 Correct 188 ms 15740 KB Output is correct
25 Correct 451 ms 63024 KB Output is correct
26 Correct 470 ms 60364 KB Output is correct
27 Correct 529 ms 63112 KB Output is correct
28 Correct 569 ms 60292 KB Output is correct
29 Correct 498 ms 63104 KB Output is correct
30 Correct 214 ms 15816 KB Output is correct
31 Correct 524 ms 63120 KB Output is correct
32 Correct 483 ms 59572 KB Output is correct
33 Correct 190 ms 15776 KB Output is correct
34 Correct 527 ms 60524 KB Output is correct
35 Correct 397 ms 58336 KB Output is correct
36 Correct 204 ms 15996 KB Output is correct
37 Correct 191 ms 15816 KB Output is correct
38 Correct 384 ms 59000 KB Output is correct
39 Correct 192 ms 58288 KB Output is correct
40 Incorrect 409 ms 58008 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 110 ms 8388 KB Output is correct
2 Correct 129 ms 8900 KB Output is correct
3 Correct 112 ms 4960 KB Output is correct
4 Correct 106 ms 8920 KB Output is correct
5 Correct 107 ms 8900 KB Output is correct
6 Correct 116 ms 8568 KB Output is correct
7 Correct 115 ms 8608 KB Output is correct
8 Correct 110 ms 9140 KB Output is correct
9 Correct 116 ms 8916 KB Output is correct
10 Correct 117 ms 12052 KB Output is correct
11 Correct 113 ms 9292 KB Output is correct
12 Correct 119 ms 12008 KB Output is correct
13 Correct 121 ms 9612 KB Output is correct
14 Correct 116 ms 11972 KB Output is correct
15 Correct 113 ms 9196 KB Output is correct
16 Correct 120 ms 12044 KB Output is correct
17 Correct 122 ms 9292 KB Output is correct
18 Correct 102 ms 3756 KB Output is correct
19 Correct 120 ms 8708 KB Output is correct
20 Correct 113 ms 4956 KB Output is correct
21 Correct 115 ms 11868 KB Output is correct
22 Correct 108 ms 8244 KB Output is correct
23 Correct 125 ms 11984 KB Output is correct
24 Correct 112 ms 8796 KB Output is correct
25 Correct 116 ms 11972 KB Output is correct
26 Correct 105 ms 8640 KB Output is correct
27 Correct 114 ms 11972 KB Output is correct
28 Correct 106 ms 8584 KB Output is correct
29 Correct 131 ms 9100 KB Output is correct
30 Correct 100 ms 8224 KB Output is correct
31 Correct 116 ms 11972 KB Output is correct
32 Correct 114 ms 11900 KB Output is correct
33 Correct 115 ms 9156 KB Output is correct
34 Correct 101 ms 8492 KB Output is correct
35 Correct 118 ms 11868 KB Output is correct
36 Correct 124 ms 9112 KB Output is correct
37 Correct 120 ms 11868 KB Output is correct
38 Correct 111 ms 9208 KB Output is correct
39 Correct 117 ms 11976 KB Output is correct
40 Correct 119 ms 9348 KB Output is correct
41 Correct 119 ms 11972 KB Output is correct
42 Correct 112 ms 9152 KB Output is correct
43 Correct 148 ms 8764 KB Output is correct
44 Correct 112 ms 9036 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 8388 KB Output is correct
2 Correct 129 ms 8900 KB Output is correct
3 Correct 112 ms 4960 KB Output is correct
4 Correct 106 ms 8920 KB Output is correct
5 Correct 107 ms 8900 KB Output is correct
6 Correct 116 ms 8568 KB Output is correct
7 Correct 115 ms 8608 KB Output is correct
8 Correct 110 ms 9140 KB Output is correct
9 Correct 116 ms 8916 KB Output is correct
10 Correct 117 ms 12052 KB Output is correct
11 Correct 113 ms 9292 KB Output is correct
12 Correct 119 ms 12008 KB Output is correct
13 Correct 121 ms 9612 KB Output is correct
14 Correct 116 ms 11972 KB Output is correct
15 Correct 113 ms 9196 KB Output is correct
16 Correct 120 ms 12044 KB Output is correct
17 Correct 122 ms 9292 KB Output is correct
18 Correct 102 ms 3756 KB Output is correct
19 Correct 686 ms 60276 KB Output is correct
20 Correct 476 ms 60292 KB Output is correct
21 Correct 458 ms 62592 KB Output is correct
22 Correct 420 ms 58628 KB Output is correct
23 Correct 192 ms 15812 KB Output is correct
24 Correct 188 ms 15740 KB Output is correct
25 Correct 451 ms 63024 KB Output is correct
26 Correct 470 ms 60364 KB Output is correct
27 Correct 529 ms 63112 KB Output is correct
28 Correct 569 ms 60292 KB Output is correct
29 Correct 498 ms 63104 KB Output is correct
30 Correct 214 ms 15816 KB Output is correct
31 Correct 524 ms 63120 KB Output is correct
32 Correct 483 ms 59572 KB Output is correct
33 Correct 190 ms 15776 KB Output is correct
34 Correct 527 ms 60524 KB Output is correct
35 Correct 397 ms 58336 KB Output is correct
36 Correct 204 ms 15996 KB Output is correct
37 Correct 191 ms 15816 KB Output is correct
38 Correct 384 ms 59000 KB Output is correct
39 Correct 192 ms 58288 KB Output is correct
40 Incorrect 409 ms 58008 KB Output isn't correct
41 Halted 0 ms 0 KB -