結果

問題 No.3763 Compress Pancakes
コンテスト
ユーザー kyoprouno
提出日時 2026-10-07 02:45:19
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.92.0 + ACL)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,704 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,886 ms
コンパイル使用メモリ 392,224 KB
実行使用メモリ 56,124 KB
最終ジャッジ日時 2026-10-09 20:53:52
合計ジャッジ時間 13,332 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 21 WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;


using ll = long long;

struct S{
	bool ex;
	ll base;
	ll sum;
	ll st;
	ll mx_val;
};

S e() {
	return {true, 0, 0, 0, 1};
}

S w() {
	return {false, -1, 0, -1, -1};
}

S op(S a, S b) {
	S res;
	res.ex = true;
	if(!a.ex || !b.ex){
		return w();
	}
	if(a.base == 0){
		return b;
	}
	if(b.base == 0){
		return a;
	}
	if(a.base != b.base){
		return w();
	} else res.base = a.base;



	ll d = abs((a.sum - a.st) + b.st);
	ll mn = min(a.mx_val, b.mx_val);

	if(d % mn != 0)return w();

	if(a.mx_val < b.mx_val){
		res.mx_val = b.mx_val;
		res.st = b.st + a.sum;
	} else {
		res.mx_val = a.mx_val;
		res.st = a.st;
	}

	res.sum = a.sum + b.sum;

	return res;
}

void main_() {
	int n,q;
	cin >> n >> q;
	vector<S> p(n);
	
	
	for(int i = 0; i < n; i++){
		ll a;
		cin >> a;
		ll a_tmp = a;
		while(a_tmp % 2 == 0)a_tmp /= 2;
		p[i].base = a_tmp;
		p[i].ex = true;
		p[i].sum = a / a_tmp;
		p[i].st = 0;
		p[i].mx_val = a / a_tmp;
	}

	segtree<S,op,e> seg(p);

	for(int i = 0; i < q; i++){
		int t;
		cin >> t;
		if(t == 1){
			int k;
			cin >> k;
			k--;
			ll x;
			cin >> x;
			S xs;
			ll x_tmp = x;
			while(x_tmp % 2 == 0)x_tmp /= 2;
			xs.base = x_tmp;
			xs.ex = true;
			xs.sum = x / x_tmp;
			xs.st = 0;
			xs.mx_val =  x / x_tmp;
			seg.set(k,xs);

		}
		if(t == 2){
			int l,r;
			cin >> l >> r;
			l--;
			S ans = seg.prod(l,r);
			bool ok = ans.ex;
			
			if(ans.st % ans.mx_val != 0 || (ans.sum - ans.st) % ans.mx_val != 0)ok = false;

			if(ok){
				cout << "Yes" << endl;
			} else {
				cout << "No" << endl;
			}
		}
	}
};

 
int main() {
	int t = 1;
	// cin >> t;
	while(t--) main_();
	return 0;
}
0