Submission #917983

#	Time	Username	Problem	Language	Result	Execution time	Memory
917983		waldi	Crossing (JOI21_crossing)	C++17	100 / 100	333 ms	34668 KiB

Main

#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, ll> pil;
ll mod = 998244353069ll;
ll pier = 71ll;

ll literka(char c){
	return c=='I' ? 0ll : (c=='J' ? 1ll : 2ll);
}

int main(){
	int n;
	scanf("%d", &n);
	vector zbior(3, vector(n+1, 0ll));
	REP(ktory, 3){
		scanf("\n");
		FOR(i, 1, n){
			char c;
			scanf("%c", &c);
			zbior[ktory][i] = literka(c);
		}
	}
	
	vector<ll> pot(n+1, 0ll);
	pot[1] = 1ll;
	FOR(i, 2, n) pot[i] = (pot[i-1]*pier)%mod;
	vector<ll> pref(n+1, 0ll);
	FOR(i, 1, n) pref[i] = (pref[i-1]+pot[i])%mod;
	auto hasz_prz = [&](int l, int p, ll lit){
		return (lit*(pref[p]-pref[l-1]+mod))%mod;
	};
	
	auto ksor = [&](vector<ll> a, vector<ll> b){
		vector<ll> ret(n+1);
		FOR(i, 1, n) ret[i] = ((a[i]+b[i])<<1)%3;
		return ret;
	};
	auto hasz_vec = [&](vector<ll> vec){
		ll ret = 0ll;
		FOR(i, 1, n) ret = (ret + pot[i]*vec[i])%mod;
		return ret;
	};
	
	zbior.emplace_back(ksor(zbior[0], zbior[1]));
	zbior.emplace_back(ksor(zbior[1], zbior[2]));
	zbior.emplace_back(ksor(zbior[0], zbior[2]));
	
	zbior.emplace_back(ksor(zbior[3], zbior[4]));
	zbior.emplace_back(ksor(zbior[4], zbior[5]));
	zbior.emplace_back(ksor(zbior[3], zbior[5]));
	
	vector<ll> zbior_haszy(ssize(zbior));
	REP(i, ssize(zbior)) zbior_haszy[i] = hasz_vec(zbior[i]);
	
	int q;
	scanf("%d\n", &q);
	set<pil> secik = {{n+1, 69ll}, {n+2, 69ll}};
	ll hasz = 0ll;
	FOR(i, 1, n){
		char c;
		scanf("%c", &c);
		ll t = literka(c);
		hasz = (hasz + pot[i]*t)%mod;
		secik.emplace(i, t);
	}
	
	FOR(i, 0, q){
		if(i){
			int l, p; char c;
			scanf("%d%d %c", &l, &p, &c);
			ll t = literka(c);
			
			auto podziel = [&](int gdzie){
				auto it = secik.lower_bound({gdzie, 0ll});
				if(it->fi == gdzie) return;
				secik.emplace(gdzie, prev(it)->se);
			};
			podziel(l), podziel(p+1);
			
			for(auto it = secik.lower_bound({l, 0ll}); it->fi <= p; it = secik.erase(it)){
				hasz = (hasz - hasz_prz(it->fi, next(it)->fi-1, it->se) + mod)%mod;
			}
			secik.emplace(l, t);
			hasz = (hasz + hasz_prz(l, p, t))%mod;
		}
		bool czy = 0;
		for(ll &x : zbior_haszy) if(x == hasz){czy = 1; break;}
		printf(czy ? "Yes\n" : "No\n");
	}
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
Main.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |   scanf("\n");
      |   ~~~~~^~~~~~
Main.cpp:26:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |    scanf("%c", &c);
      |    ~~~~~^~~~~~~~~~
Main.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d\n", &q);
      |  ~~~~~^~~~~~~~~~~~
Main.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |   scanf("%c", &c);
      |   ~~~~~^~~~~~~~~~
Main.cpp:77:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |    scanf("%d%d %c", &l, &p, &c);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 23 / 23
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51