結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー 小高悠太郎
提出日時 2025-01-14 10:14:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 440 ms / 5,000 ms
コード長 2,315 bytes
コンパイル時間 3,506 ms
コンパイル使用メモリ 286,532 KB
実行使用メモリ 31,872 KB
最終ジャッジ日時 2025-01-14 10:14:49
合計ジャッジ時間 7,201 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vec = vector<ll>;
using mat = vector<vec>;
using matx = vector<mat>; using maty = vector<matx>;
const int INF = 1073741823;
const ll INFl = 1LL << 60;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

struct LazySegTree {
	int n;
	mat node, lazy;

	LazySegTree(int N) {
		n = 1;
		while(n < N) n*=2;
		node.resize(2*n, vec(2, 0));
		lazy.resize(2*n, vec(2, 0));
	}
  void eval(int pos, int bottom, int top) {
		if(lazy[pos][0] > 0 || lazy[pos][1] > 0) {
			node[pos][0] = lazy[pos][0];
			node[pos][1] = lazy[pos][1];
			if(top-bottom > 1) {
				lazy[pos*2][0] = lazy[pos][0]/2; 
				lazy[pos*2][1] = lazy[pos][1]/2; 
				lazy[pos*2+1][0] = lazy[pos][0]/2; 
				lazy[pos*2+1][1] = lazy[pos][1]/2; 
			}
			lazy[pos][0] = 0; lazy[pos][1] = 0;
		}
	}
	void update(int l, int r, int x, int pos=1, int bottom=0, int top=-1) {
		if(top == -1) top = n;
		eval(pos, bottom, top);
		if(top <= l || r <= bottom) return;
		if(l <= bottom && top <= r) {
			lazy[pos][x] = (top-bottom);
			eval(pos, bottom, top);
		}
		else {
			int mid = (bottom+top)/2;
			update(l, r, x, 2*pos, bottom, mid);
			update(l, r, x, 2*pos+1, mid, top);
			node[pos][0] = node[pos*2][0] + node[pos*2+1][0];
			node[pos][1] = node[pos*2][1] + node[pos*2+1][1];
		}
	}
	vec get_sum(int l, int r, int pos=1, int bottom=0, int top=-1) {
		if(top == -1) top = n;
	  if(top <= l || r <= bottom) return {0, 0};
		eval(pos, bottom, top);
		if(l <= bottom && top <= r) {
			return node[pos];
		}
		else {
			int mid = (bottom+top)/2;
      vec
			L = get_sum(l, r, 2*pos, bottom, mid),
			R = get_sum(l, r, 2*pos+1, mid, top);
			return{L[0]+R[0], L[1]+R[1]};
		}
	}
};



int main() {
  int n, q; cin >> n >> q;
	LazySegTree tree(n);
	ll a=0, b=0;
	rep(i, q) {
		int x; cin >> x;
		if(x == 0) {
			int l, r; cin >> l >> r;
			vec A(2);
			A = tree.get_sum(l, r+1);

			if(A[0] < A[1]) b+=A[1];
			else if(A[0] > A[1]) a+=A[0];
		}
		else if(x == 1) {
			int l, r; cin >> l >> r;
			tree.update(l, r+1, 0);
		}
		else {
			int l, r; cin >> l >> r;
			tree.update(l, r+1, 1);
		}
	}
	vec B = tree.get_sum(0, n);
	a += B[0];
	b += B[1];
	cout << a << " " << b << endl;


    
}
0