Submission #891317

#	Time	Username	Problem	Language	Result	Execution time	Memory
891317		iris2617	Crossing (JOI21_crossing)	C++14	100 / 100	1933 ms	215948 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define matsuri pair<int,int>
//const int iris = 1e9+7;
const int iris = 998244353;
using namespace std;

map<char, int> dd;

struct sagiri
{
	int n;
	vector<int> arr;
	vector<int> owo;
	vector<int> st;
	vector<int> tag;
	sagiri(const vector<int> &a)
	{
		n=a.size();
		arr=a;
		owo.resize(n*4);
		st.resize(n*4);
		tag.resize(n*4);
	}
	void build(int i,int l,int r, vector<int> & brr)
	{
		if(l==r)
		{
			owo[i]=arr[l];
			st[i]=(arr[l]==brr[l]);
		}
		else
		{
			int m=l+(r-l)/2;
			build(i*2,l,m,brr);
			build(i*2+1,m+1,r,brr);
			if(owo[i*2]==owo[i*2+1])
				owo[i]=owo[i*2];
			else
				owo[i]=4;
			st[i]=st[i*2]&st[i*2+1];
		}
		//cout<<' '<<i<<' '<<l<<' '<<r<<' '<<st[i]<<'\n';
	}
	void push(int i,int l,int r)
	{
		if(!tag[i] || l==r)
			return;
		l=i*2, r=i*2+1;
		tag[l]=tag[r]=tag[i];
		st[l]=(owo[l]==tag[i]);
		st[r]=(owo[r]==tag[r]);
		tag[i]=0;
	}
	void mdf(int i,int l,int r,int L,int R,int x)
	{
		push(i,l,r);
		int m=l+(r-l)/2;
		if(L<=l && r<=R)
		{
			st[i]=(owo[i]==x), tag[i]=x;
			return;
		}
		if(L<=m)
			mdf(i*2,l,m,L,R,x);
		if(R>m)
			mdf(i*2+1,m+1,r,L,R,x);
		st[i]=st[i*2]&st[i*2+1];
	}
};

void solve()
{
	dd['J']=1;
	dd['O']=2;
	dd['I']=3;
	int n;
	cin>>n;
	vector<vector<int> > owo;
	set<vector<int> > st;
	auto pr=[&](vector<int> v)
	{
		for(int x:v)
			cout<<x;
		cout<<'\n';
	};
	auto pp=[&](string s)
	{
		vector<int> res;
		for(char c:s)
			res.emplace_back(dd[c]);
		return res;
	};
	for(int i=0;i<3;i++)
	{
		string s;
		cin>>s;
		auto v=pp(s);
		st.insert(v);
		owo.emplace_back(v);
	}
	auto cal=[&](vector<int> a,vector<int> b)
	{
		for(int i=0;i<a.size();i++)
			a[i]=(6-a[i]+1-b[i]+1)%3+1;
		return a;
	};
	while(1)
	{
		bool flag=0;
		int n=owo.size();
		for(int i=0;i<n;i++)
		{
			for(int j=i;j<n;j++)
			{
				auto v=cal(owo[i], owo[j]);
				if(st.count(v)==0)
				{
					flag=1;
					st.insert(v);
					owo.emplace_back(v);
				}
			}
		}
		if(!flag)
			break;
	}
	
	vector<sagiri> sarina;
	int q;
	cin>>q;
	string s;
	cin>>s;
	auto brr=pp(s);
	bool ok=0;
	for(int i=0;i<owo.size();i++)
	{
		sarina.emplace_back(sagiri(owo[i]));
		sarina.back().build(1,0,n-1,brr);
		ok|=sarina.back().st[1];
		//pr(owo[i]);
	}
	if(ok)
		cout<<"Yes\n";
	else
		cout<<"No\n";
	while(q--)
	{
		int l,r;
		char c;
		cin>>l>>r>>c;
		l--, r--;
		int x=dd[c];
		bool ok=0;
		for(auto &ss:sarina)
		{
			ss.mdf(1,0,n-1,l,r,x);
			ok|=ss.st[1];
		}
		if(ok)
			cout<<"Yes\n";
		else
			cout<<"No\n";
	}
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
	
	int T=1;
	//cin>>T;
	while(T--)
		solve();
	
    return 0;
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:104:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for(int i=0;i<a.size();i++)
      |               ~^~~~~~~~~
Main.cpp: In function 'void solve()':
Main.cpp:136:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  for(int i=0;i<owo.size();i++)
      |              ~^~~~~~~~~~~
Main.cpp:81:7: warning: variable 'pr' set but not used [-Wunused-but-set-variable]
   81 |  auto pr=[&](vector<int> v)
      |       ^~

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