結果

問題 No.924 紲星
コンテスト
ユーザー fgwiebfaoish
提出日時 2020-02-20 03:58:05
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,925 ms / 4,000 ms
コード長 4,724 bytes
コンパイル時間 3,569 ms
コンパイル使用メモリ 109,056 KB
実行使用メモリ 118,412 KB
最終ジャッジ日時 2024-10-08 18:40:05
合計ジャッジ時間 19,581 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
static class Program{
	const int mod=(int)1e9+7;
	static void Main(){
		Sc sc=new Sc();
		var s=sc.Ia;
		var a=sc.Ia;
		int p=0,n=s[0],q=s[1];
		var g=new int[n][];
		int[] la=new int[n],ua=new int[n];
		var z=new int[q][];
		var liq=new List<int>[n];
		var qe=new int[q][];
		for(int i = 0;i<n;i++) {
			g[i]=new int[]{i+1,a[i]};
			liq[i]=new List<int>();
		}
		Array.Sort(g,(u,v)=>v[1]-u[1]);
		int mid=(n-1)>>1;
		la[mid]=-1;
		ua[mid]=n;
		for(int i = 0;i<q;i++) {
			qe[i]=sc.Ia3(false,0,true,0);
			qe[i][2]=(qe[i][1]-qe[i][0]+2)>>1;
			liq[mid].Add(i);
		}
		while(p<q){
			Bit bit1=new Bit(n);
			for(int i = 0;i<n;i++) {
				bit1.Ud(g[i][0],1);
				if(liq[i].Count!=0){
					for(int j = 0;j<liq[i].Count;j++) {
						int lb=i,ub=i;
						if(bit1.Get2(qe[liq[i][j]][0],qe[liq[i][j]][1])>=qe[liq[i][j]][2]){
							mid=(la[i]+i)>>1;
							lb=la[i];
						}
						else{
							mid=(ua[i]+i)>>1;
							ub=ua[i];
						}
						if(ub-lb>1){
							liq[mid].Add(liq[i][j]);
							la[mid]=lb;
							ua[mid]=ub;
						}
						else{
							z[liq[i][j]]=new int[]{g[ub][1],liq[i][j]};
							p++;
						}
					}
				}
				liq[i].Clear();
			}
		}
		Bit bit2=new Bit(n);
		Bit bit3=new Bit(n);
		var ans=new long[q];
		var x=new long[q];
		var y=new long[q];
		Array.Sort(z,(u,v)=>u[0]-v[0]);
		for(int i = n-1,j=0;i>=0;i--) {
			bit2.Ud(g[i][0],g[i][1]);
			bit3.Ud(g[i][0],1);
			while(j<q&&(z[j][0]==g[i][1])){
				x[z[j][1]]=bit2.Get2(qe[z[j][1]][0],qe[z[j][1]][1]);
				y[z[j][1]]=bit3.Get2(qe[z[j][1]][0],qe[z[j][1]][1]);
				ans[z[j][1]]=y[z[j][1]]*z[j][0]-x[z[j][1]];
				j++;
			}
		}
		for(int i = 0;i<q;i++) {
			ans[z[i][1]]+=(bit2.Get2(qe[z[i][1]][0],qe[z[i][1]][1])-x[z[i][1]])-(qe[z[i][1]][1]-qe[z[i][1]][0]+1-y[z[i][1]])*z[i][0];
		}
		Console.WriteLine("{0}",String.Join("\n",ans));
	}
}
public class Bit{
	private int n;
	private long[] bit;
	public Bit(int n){
		this.n=n;
		bit=new long[n+1];
	}
	public void Ud(int a,long p){while(a<=n){bit[a]+=p;a+=a&-a;}}
	public long Get(int n){
		long a=0;
		while(n>0){a+=bit[n];n-=n&-n;}
		return a;
	}
	public long Get2(int m,int n){
		long a=0,b=0;
		m--;
		while(n>m){a+=bit[n];n-=n&-n;}
		if(n==m){return a;}
		while(n!=m){b+=bit[m];m-=m&-m;}
		return a-b;
	}
	public void Clear(){bit=new long[n+1];}
}
public class Sc{
	public int I{get{return int.Parse(Console.ReadLine());}}
	public long L{get{return long.Parse(Console.ReadLine());}}
	public double D{get{return double.Parse(Console.ReadLine());}}
	public string S{get{return Console.ReadLine();}}
	public int[] Ia{get{return Array.ConvertAll(Console.ReadLine().Split(),int.Parse);}}
	public long[] La{get{return Array.ConvertAll(Console.ReadLine().Split(),long.Parse);}}
	public double[] Da{get{return Array.ConvertAll(Console.ReadLine().Split(),double.Parse);}}
	public string[] Sa{get{return Console.ReadLine().Split();}}
	public object[] Oa{get{return Console.ReadLine().Split();}}
	public int[] Ia2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),int.Parse);}}
	public int[] Ia3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),int.Parse);}
	public int[] Ia3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),int.Parse);}
	public long[] La2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),long.Parse);}}
	public long[] La3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),long.Parse);}
	public long[] La3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),long.Parse);}
	public double[] Da2{get{return Array.ConvertAll(("0 "+Console.ReadLine()+" 0").Split(),double.Parse);}}
	public double[] Da3(int a){return Array.ConvertAll((a.ToString()+" "+Console.ReadLine()).Split(),double.Parse);}
	public double[] Da3(bool a,int b,bool c,int d){return Array.ConvertAll(((a?b.ToString()+" ":"")+Console.ReadLine()+(c?" "+d.ToString():"")).Split(),double.Parse);}
	public T[] Arr<T>(int n,Func<T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f();}return a;}
	public T[] Arr<T>(int n,Func<int,T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i);}return a;}
	public T[] Arr<T>(int n,Func<string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(Console.ReadLine().Split());}return a;}
	public T[] Arr<T>(int n,Func<int,string[],T> f){var a=new T[n];for(int i=0;i<n;i++){a[i]=f(i,Console.ReadLine().Split());}return a;}
}
0