제출 #915624

#제출 시각아이디문제언어결과실행 시간메모리
915624qinCrossing (JOI21_crossing)C++17
26 / 100
686 ms63120 KiB
    #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;
    }

컴파일 시 표준 에러 (stderr) 메시지

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...