結果

問題 No.924 紲星
ユーザー uwiuwi
提出日時 2019-11-08 23:04:48
言語 Java21
(openjdk 21)
結果
AC  
実行時間 2,141 ms / 4,000 ms
コード長 6,695 bytes
コンパイル時間 4,457 ms
コンパイル使用メモリ 91,712 KB
実行使用メモリ 214,552 KB
最終ジャッジ日時 2023-10-13 04:41:43
合計ジャッジ時間 22,765 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
49,524 KB
testcase_01 AC 41 ms
49,020 KB
testcase_02 AC 40 ms
49,520 KB
testcase_03 AC 57 ms
49,284 KB
testcase_04 AC 47 ms
49,168 KB
testcase_05 AC 57 ms
49,636 KB
testcase_06 AC 59 ms
49,580 KB
testcase_07 AC 46 ms
49,096 KB
testcase_08 AC 2,102 ms
213,092 KB
testcase_09 AC 2,080 ms
212,096 KB
testcase_10 AC 2,141 ms
214,552 KB
testcase_11 AC 2,133 ms
210,504 KB
testcase_12 AC 1,910 ms
214,368 KB
testcase_13 AC 890 ms
113,544 KB
testcase_14 AC 749 ms
89,748 KB
testcase_15 AC 763 ms
110,820 KB
testcase_16 AC 1,321 ms
189,784 KB
testcase_17 AC 1,060 ms
113,732 KB
testcase_18 AC 42 ms
49,564 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package contest191108;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni(), Q = ni();
		int[] a = na(n);
		long[] cum = new long[n+1];
		for(int i = 0;i < n;i++)cum[i+1] = cum[i] + a[i];
		Node[] rs = makeEntries(a);
		for(int i = 0;i < Q;i++) {
			int L = ni()-1, R = ni()-1+1;
			int val = kth(rs[L], rs[R], (R-L)/2);
			long minor = sumFirstK(rs[L], rs[R], (R-L)/2);
			long major = cum[R] - cum[L] - minor;
			out.println(major - (long)val*(R-L-(R-L)/2) + (val*((long)(R-L)/2) - minor));
		}
	}
	
	public static class Node
	{
		public int num;
		public int count;
		public int des;
		public long sum;
		public Node left, right;
		
		public Node(int num, int count, long sum) {
			this.num = num;
			this.count = count;
			this.sum = sum;
			des = count;
		}
		
		public Node clone()
		{
			Node ret = new Node(num, count, sum);
			ret.left = this.left;
			ret.right = this.right;
			return ret;
		}
		
		public void update()
		{
			des = count;
			sum = (long)num * count;
			if(left != null){
				des += left.des;
				sum += left.sum;
			}
			if(right != null){
				des += right.des;
				sum += right.sum;
			}
		}
		
		public Node insert(int x)
		{
			if(x < num){
				left = left.clone();
				left.insert(x);
			}else if(x > num){
				right = right.clone();
				right.insert(x);
			}else{
				count++; // e is always cloned.
			}
			update();
			return this;
		}
		
		public Node erase(int x)
		{
			if(x < num){
				left = left.clone();
				left.erase(x);
			}else if(x > num){
				right = right.clone();
				right.erase(x);
			}else{
				count--; // e is always cloned.
			}
			update();
			return this;
		}
		
		public String toString(String indent) {
			StringBuilder builder = new StringBuilder();
			if(left != null){
				builder.append(left.toString(indent + "  "));
			}
			builder.append("[num=");
			builder.append(num);
			builder.append(", count=");
			builder.append(count);
			builder.append(", des=");
			builder.append(des);
			builder.append(", sum=");
			builder.append(sum);
			builder.append("]\n");
			if(right != null){
				builder.append(right.toString(indent + "  "));
			}
			return builder.toString();
		}
	}
	
	public static long sumFirstK(Node X, Node Y, int K)
	{
		long alsum = 0;
		while(K > 0){
			Node XL = X.left, YL = Y.left;
			if(XL != null && K < YL.des - XL.des){
				X = XL; Y = YL;
			}else{
				if(XL != null){
					K -= YL.des - XL.des;
					alsum += YL.sum - XL.sum;
				}
				if(K < Y.count - X.count){
					alsum += (long)Y.num * K;
					break;
				}else{
					alsum += (long)Y.num * (Y.count - X.count);
					K -= Y.count - X.count;
					X = X.right; Y = Y.right;
				}
			}
		}
		return alsum;
	}
	
	public static int kth(Node X, Node Y, int K)
	{
		while(true){
			Node XL = X.left, YL = Y.left;
			if(XL != null && K < YL.des - XL.des){
				X = XL; Y = YL;
			}else{
				if(XL != null){
					K -= YL.des - XL.des;
				}
				if(K < Y.count - X.count){
					return Y.num;
				}else{
					K -= Y.count - X.count;
					X = X.right; Y = Y.right;
				}
			}
		}
	}
	
	public static Node[] makeEntries(int[] a)
	{
		int n = a.length;
		Node[] entry = new Node[n+1];
		entry[0] = buildPBST(a);
		for(int i = 0;i < n;i++){
			entry[i+1] = entry[i].clone().insert(a[i]);
		}
		return entry;
	}
	
	public static Node buildPBST(int[] oa){
		int n = oa.length;
		int[] a = Arrays.copyOf(oa, n);
		Arrays.sort(a);
		int[] b = new int[n];
		int p = 0;
		for(int i = 0;i < n;i++){
			if(i == 0 || a[i] != a[i-1]){
				b[p++] = a[i];
			}
		}
		b = Arrays.copyOf(b, p);
		return dfs(0, p, b);
	}
	
	private static Node dfs(int l, int r, int[] b)
	{
		if(l == r)return null;
		int m = l+r>>>1;
		Node ret = new Node(b[m], 0, 0L);
		ret.left = dfs(l, m, b);
		ret.right = dfs(m+1, r, b);
		return ret;
	}
	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//		Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//			@Override
//			public void run() {
//				long s = System.currentTimeMillis();
//				solve();
//				out.flush();
//				if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//			}
//		};
//		t.start();
//		t.join();
	}
	
	public static void main(String[] args) throws Exception { new E().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private long[] nal(int n)
	{
		long[] a = new long[n];
		for(int i = 0;i < n;i++)a[i] = nl();
		return a;
	}
	
	private char[][] nm(int n, int m) {
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[][] nmi(int n, int m) {
		int[][] map = new int[n][];
		for(int i = 0;i < n;i++)map[i] = na(m);
		return map;
	}
	
	private int ni() { return (int)nl(); }
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
0