結果

問題 No.3763 Compress Pancakes
コンテスト
ユーザー kotatsugame
提出日時 2026-10-09 23:19:12
言語 C++14
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,916 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 513 ms
コンパイル使用メモリ 102,324 KB
実行使用メモリ 45,716 KB
最終ジャッジ日時 2026-10-09 23:19:19
合計ジャッジ時間 5,959 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:89:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   89 |                 auto[a,k]=mk(A);
      |                     ^
main.cpp:101:29: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  101 |                         auto[a,k]=mk(x);
      |                             ^

ソースコード

diff #
raw source code 

#include<iostream>
#include<cassert>
#include<atcoder/segtree>
using namespace std;
struct dat{
	int mx;
	long lft,rgt;
};
dat op(dat a,dat b)
{
	if(a.mx==-1)return b;
	if(b.mx==-1)return a;
	if(a.mx==-2)return(dat){-2,0L,0L};
	if(b.mx==-2)return(dat){-2,0L,0L};
	long l=a.rgt,r=b.lft;
	l|=1L<<a.mx;
	r|=1L<<b.mx;
	while(l&&r)
	{
		long k=l&-l;
		long kk=r&-r;
		if(k!=kk)
		{
			if(k<kk&&l==k)
			{
				r|=k;
				l=0;
				break;
			}
			if(k>kk&&r==kk)
			{
				l|=kk;
				r=0;
				break;
			}
			return(dat){-2,0L,0L};
		}
		l^=k;
		r^=k;
		k<<=1;
		if(!(l&k))l|=k;
		else if(!(r&k))r|=k;
		else return(dat){-2,0L,0L};
	}
	assert(l||r);
	dat ret;
	ret.lft=a.lft;
	ret.rgt=b.rgt;
	if(l)
	{
		int k=0;
		while(l>>k+1)k++;
		ret.mx=k;
		ret.rgt|=l^(1L<<k);
	}
	else
	{
		int k=0;
		while(r>>k+1)k++;
		ret.mx=k;
		ret.lft|=r^(1L<<k);
	}
	return ret;
}
dat e(){return(dat){-1,0L,0L};}
pair<int,int>mk(int a)
{
	int k=0;
	while(a%2==0)a/=2,k++;
	return make_pair(a,k);
}
pair<int,int>op_minmax(pair<int,int>l,pair<int,int>r)
{
	l.first=max(l.first,r.first);
	l.second=min(l.second,r.second);
	return l;
}
pair<int,int>e_minmax(){return make_pair(-(int)1e9,(int)1e9);}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,Q;cin>>N>>Q;
	vector<pair<int,int> >init_minmax(N);
	vector<dat>init(N);
	for(int i=0;i<N;i++)
	{
		int A;cin>>A;
		auto[a,k]=mk(A);
		init[i]=(dat){k,0L,0L};
		init_minmax[i]=make_pair(a,a);
	}
	atcoder::segtree<dat,op,e>seg(init);
	atcoder::segtree<pair<int,int>,op_minmax,e_minmax>seg_minmax(init_minmax);
	for(;Q--;)
	{
		int t;cin>>t;
		if(t==1)
		{
			int i,x;cin>>i>>x;i--;
			auto[a,k]=mk(x);
			seg.set(i,(dat){k,0L,0L});
			seg_minmax.set(i,make_pair(a,a));
		}
		else
		{
			int l,r;cin>>l>>r;l--;
			auto p=seg_minmax.prod(l,r);
			if(p.first!=p.second)cout<<"No\n";
			else
			{
				dat t=seg.prod(l,r);
				cout<<(t.mx==-2||t.lft||t.rgt?"No\n":"Yes\n");
			}
		}
	}
}
0