結果

問題 No.3763 Compress Pancakes
コンテスト
ユーザー kotatsugame
提出日時 2026-10-09 23:37:23
言語 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
結果
AC  
実行時間 257 ms / 2,000 ms
+ 588µs
コード長 1,971 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 661 ms
コンパイル使用メモリ 108,796 KB
実行使用メモリ 42,644 KB
最終ジャッジ日時 2026-10-09 23:38:01
合計ジャッジ時間 6,336 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge5_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 29
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:54:21: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   54 |                 auto[a,k]=mk(A);
      |                     ^
main.cpp:69:29: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
   69 |                         auto[a,k]=mk(x);
      |                             ^

ソースコード

diff #
raw source code 

#include<iostream>
#include<cassert>
#include<atcoder/fenwicktree>
#include<atcoder/segtree>
#include<atcoder/lazysegtree>
using namespace std;
struct dat{
	int mx;
	long S;
};
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};
	if(b.mx==-2)return(dat){-2,0L};
	if(a.mx<b.mx)swap(a.mx,b.mx),swap(a.S,b.S);
	if((a.S&(1L<<b.mx)-1)!=b.S)return(dat){-2,0L};
	return a;
}
dat e(){return(dat){-1,0L};}
dat mp(long f,dat x)
{
	x.S=(x.S+f)&(1L<<x.mx)-1;
	return x;
}
long cmp(long f,long g){return f+g;}
long id(){return 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);
	atcoder::fenwick_tree<long>BIT(N);
	vector<int>K(N);
	for(int i=0;i<N;i++)
	{
		int A;cin>>A;
		auto[a,k]=mk(A);
		K[i]=k;
		BIT.add(i,1L<<k);
		long S=BIT.sum(0,i);
		init[i]=(dat){k,S&(1L<<k)-1};
		init_minmax[i]=make_pair(a,a);
	}
	atcoder::lazy_segtree<dat,op,e,long,mp,cmp,id>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);
			BIT.add(i,(1L<<k)-(1L<<K[i]));
			seg.apply(i+1,N,(1L<<k)-(1L<<K[i]));
			K[i]=k;
			long S=BIT.sum(0,i);
			seg.set(i,(dat){k,S&(1L<<k)-1});
			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
			{
				long sum=BIT.sum(l,r);
				if(sum!=(sum&-sum))cout<<"No\n";
				else
				{
					dat t=seg.prod(l,r);
					long S=BIT.sum(0,l);
					cout<<(t.mx==-2||t.S!=(S&(1L<<t.mx)-1)?"No\n":"Yes\n");
				}
			}
		}
	}
}
0