結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー uafr_csuafr_cs
提出日時 2017-11-05 23:26:45
言語 Java21
(openjdk 21)
結果
AC  
実行時間 582 ms / 5,000 ms
コード長 3,765 bytes
コンパイル時間 2,386 ms
コンパイル使用メモリ 75,112 KB
実行使用メモリ 69,996 KB
最終ジャッジ日時 2023-08-15 18:47:21
合計ジャッジ時間 9,396 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 72 ms
50,700 KB
testcase_01 AC 75 ms
50,672 KB
testcase_02 AC 81 ms
52,616 KB
testcase_03 AC 78 ms
52,612 KB
testcase_04 AC 77 ms
52,236 KB
testcase_05 AC 131 ms
54,376 KB
testcase_06 AC 198 ms
56,592 KB
testcase_07 AC 130 ms
54,184 KB
testcase_08 AC 168 ms
55,324 KB
testcase_09 AC 426 ms
62,404 KB
testcase_10 AC 416 ms
58,064 KB
testcase_11 AC 342 ms
59,968 KB
testcase_12 AC 422 ms
62,172 KB
testcase_13 AC 223 ms
56,276 KB
testcase_14 AC 357 ms
68,224 KB
testcase_15 AC 506 ms
69,940 KB
testcase_16 AC 538 ms
69,648 KB
testcase_17 AC 582 ms
69,604 KB
testcase_18 AC 464 ms
69,996 KB
testcase_19 AC 478 ms
69,580 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package jp.monyone.verify.yukicoder.No230.LazySetSumSegmentTree;



import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStream;

import java.io.InputStreamReader;

import java.util.StringTokenizer;



public class Main {



	// 以下のクエリに対応するデータ構造

	// set : [l, r) の値を一定にするクエリ

	// sum : [l, r) の合計を取得するクエリ

	public static class LazySetSumSegmentTree {

		int n;



		long[] dat, lazy;

		boolean[] push;



		public LazySetSumSegmentTree(int n_) {

			int n = 1;

			while(n < n_){ n *= 2;} this.n = n;



			dat = new long[this.n * 2 - 1];

			lazy = new long[this.n * 2 - 1];

			push = new boolean[this.n * 2 - 1];

		}



		// [a, b) の区間で set の遅延してる分を評価する

		private void evaluate_lazy(int k, int l, int r){

			if(!push[k]){ return; }



			dat[k] = lazy[k] * (r - l);

			if(k < n - 1){

				lazy[k * 2 + 1] = lazy[k * 2 + 2] = lazy[k];

				push[k * 2 + 1] = push[k * 2 + 2] = true;

			}



			lazy[k] = 0;

			push[k] = false;

		}



		private void update_node(int k){

			dat[k] = dat[k * 2 + 1] + dat[k * 2 + 2];

		}



		public void set(long v, int a, int b){ set(v, a, b, 0, 0, this.n); }

		public void set(long v, int a, int b, int k, int l, int r){

			evaluate_lazy(k, l, r);

			if(r <= a || b <= l){ return;

			}else if(a <= l && r <= b){

				lazy[k] = v;

				push[k] = true;

				evaluate_lazy(k, l, r);

			}else{

				set(v, a, b, k * 2 + 1, l, (l + r) / 2);

				set(v, a, b, k * 2 + 2, (l + r) / 2, r);

				update_node(k);

			}

		}



		public long sum(int a, int b){ return sum(a, b, 0, 0, this.n); }

		public long sum(int a, int b, int k, int l, int r){

			evaluate_lazy(k, l, r);

			if(r <= a || b <= l){ return 0;

			}else if(a <= l && r <= b){ return dat[k];

			}else{

				final long v1 = sum(a, b, k * 2 + 1, l, (l + r) / 2);

				final long v2 = sum(a, b, k * 2 + 2, (l + r) / 2, r);

				update_node(k); return v1 + v2;

			}

		}

	}

	

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		

		final int N = sc.nextInt();

		final int Q = sc.nextInt();

		

		long a_score = 0, b_score = 0;

		

		LazySetSumSegmentTree a_seg = new LazySetSumSegmentTree(N);

		LazySetSumSegmentTree b_seg = new LazySetSumSegmentTree(N);

		

		for(int i = 0; i < Q; i++){

			final int x = sc.nextInt();

			final int l = sc.nextInt();

			final int r = sc.nextInt() + 1;

			

			if(x == 0){

				final long a_team = a_seg.sum(l, r);

				final long b_team = b_seg.sum(l, r);

				

				if(a_team > b_team){

					a_score += a_team;

				}else if(a_team < b_team){

					b_score += b_team;

				}

			

			}else if(x == 1){

				a_seg.set(1, l, r);

				b_seg.set(0, l, r);

			}else if(x == 2){

				a_seg.set(0, l, r);

				b_seg.set(1, l, r);

			}

		}

		

		a_score += a_seg.sum(0, N);

		b_score += b_seg.sum(0, N);

		

		System.out.println(a_score + " " + b_score);

	}

	

	public static class Scanner implements AutoCloseable {

		private BufferedReader br;

		private StringTokenizer tok;



		public Scanner(InputStream is) {

			br = new BufferedReader(new InputStreamReader(is));

		}



		private void getLine() {

			try {

				while (!hasNext()) {tok = new StringTokenizer(br.readLine());}

			} catch(IOException e){ /* ignore */ }

		}



		private boolean hasNext() {

			return tok != null && tok.hasMoreTokens();

		}



		public String next() {

			getLine(); return tok.nextToken();

		}



		public int nextInt(){

			return Integer.parseInt(next());

		}

		// 他のnextXXXもXXX.parseXXX()メソッドを使って作れるので省略



		public void close() {

			try{ br.close(); } catch (IOException e){ /*ignore*/ }

		}

	}

	

}
0