結果

問題 No.3164 [Chery 7th Tune B] La vie en rose
コンテスト
ユーザー msksknkn
提出日時 2025-06-28 14:44:31
言語 Java
(openjdk 23)
結果
AC  
実行時間 1,581 ms / 2,000 ms
コード長 1,784 bytes
コンパイル時間 2,908 ms
コンパイル使用メモリ 81,360 KB
実行使用メモリ 87,772 KB
最終ジャッジ日時 2025-06-28 14:45:16
合計ジャッジ時間 42,622 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff # 

package no3164_la_vie_en_rose;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		UnionFind uf = new UnionFind(n + 1);
		for(int i = 1;i <= n;i++) {
			uf.val[i] = Integer.parseInt(sc.next());
			uf.size[i] = uf.val[i];
		}for(int i = 1;i <= n;i++) {
			if(uf.val[i - 1] > 0 && uf.val[i] > 0) {
				uf.unite(i - 1, i);
			}	
		}int q = sc.nextInt();
		StringBuilder sb = new StringBuilder();
		for(int i = 0;i < q;i++){
			int ind = Integer.parseInt(sc.next());
			int val = Integer.parseInt(sc.next());
			long ans = 0;
			int root = uf.getRoot(ind);
			if(uf.val[ind] == 0) {
				int b = uf.getRoot(ind - 1);
				int c = uf.getRoot(ind + 1);
				ans = val + uf.size[b] + uf.size[c];
			}else {
				ans = uf.size[root] + val - uf.val[ind];
			}
			sb.append(ans + "\n");
		}System.out.print(sb);
	}public static class UnionFind{
		  public int[] root;
		  public long[] size;
		  public long[] val;
		  public UnionFind(int n) {
			  this.root = new int[n + 1];
			  this.size = new long[n + 1];
			  this.val = new long[n + 1];
			  for(int i = 1;i < n + 1;i++) {
				  this.root[i] = i;
			  }
		  }
		  public void unite(int x,int y) {
			  x = getRoot(x);
			  int yc = getRoot(y);
			  if(x != y){
				  size[x] += size[yc];
			  }
			  this.root[yc] = this.root[x];
		  }
		  public void rootPlus(int x,int y) {
			  this.root[x] = y;
			  this.size[y]++;
		  }
		  
		  public int getRoot(int x) {
			  if(x == this.root[x]) {
				  return x;
			  }else
			  return this.root[x] = getRoot(this.root[x]);
		  }
		  public boolean same(int x,int y) {
			  x = getRoot(x);
			  y = getRoot(y);
			  return x == y;
		  }
	}

}
0