結果
| 問題 |
No.924 紲星
|
| コンテスト | |
| ユーザー |
 紙ぺーぱー
|
| 提出日時 | 2019-11-08 22:40:08 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 2,660 ms / 4,000 ms |
| コード長 | 7,287 bytes |
| コンパイル時間 | 2,786 ms |
| コンパイル使用メモリ | 116,772 KB |
| 実行使用メモリ | 92,064 KB |
| 最終ジャッジ日時 | 2024-09-15 01:52:38 |
| 合計ジャッジ時間 | 23,380 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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.
ソースコード
//author: camypaper
using System;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;
using Debug = System.Diagnostics.Debug;
using SB = System.Text.StringBuilder;
using System.Numerics;
using Point = System.Numerics.Complex;
using static System.Math;
using Number = System.Int64;
using System.Runtime.CompilerServices;
namespace Program {
public class Solver {
Random rnd = new Random(0);
public void Solve() {
var n = ri;
var q = ri;
var a = Enumerate(n, x => ri);
var xs = a.Distinct().ToList(); xs.Sort();
var K = xs.Count;
var Q = Enumerate(q, x => new int[] { ri, ri });
var fenwick = new FenwickTree(n);
var L = Enumerate(q, x => 0);
var R = Enumerate(q, x => K - 1);
var X = Enumerate(q, x => 0);
var ev = Enumerate(K, x => new List<int>());
for (int i = 0; i < n; i++)
ev[xs.BinarySearch(a[i])].Add(i);
for (int T = 0; T < 20; T++) {
for (int i = 0; i < q; i++) {
X[i] = (L[i] + R[i]) / 2;
ev[X[i]].Add(100000000 + i);
}
for (int i = 0; i < K; i++)
foreach (var e in ev[i]) {
if (e < n) fenwick.Add(e + 1, 1);
else {
var id = e - 100000000;
var cnt = fenwick[Q[id][0], Q[id][1]];
var len = Q[id][1] - Q[id][0] + 1;
if (cnt >= (len + 1) / 2) R[id] = X[id];
else L[id] = X[id];
}
}
for (int i = 0; i < q; i++) {
ev[X[i]].RemoveAt(ev[X[i]].Count - 1);
}
for (int i = 0; i < K; i++)
foreach (var e in ev[i]) {
if (e < n) fenwick.Add(e + 1, -1);
}
}
Debug.WriteLine(R.AsJoinedString());
var rem = new FenwickTree(n);
var use = new FenwickTree(n);
var ans = new long[q];
for (int i = 0; i < n; i++)
rem.Add(i + 1, a[i]);
for (int i = 0; i < q; i++)
ev[R[i]].Add(100000000 + i);
for (int i = 0; i < K; i++) {
foreach (var e in ev[i]) {
if (e < n) {
fenwick.Add(e + 1, 1);
use.Add(e + 1, a[e]);
rem.Add(e + 1, -a[e]);
}
else {
var id = e - 100000000;
var cnt = fenwick[Q[id][0], Q[id][1]];
ans[id] += cnt * xs[i] - use[Q[id][0], Q[id][1]];
var len = Q[id][1] - Q[id][0] + 1;
ans[id] += rem[Q[id][0], Q[id][1]] - (len - cnt) * xs[i];
}
}
}
foreach (var x in ans)
Console.WriteLine(x);
}
const long INF = 1L << 60;
int ri => sc.Integer();
long rl => sc.Long();
double rd => sc.Double();
string rs => sc.Scan();
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static IEnumerable<int> Rep(int n) => Enumerable.Range(0, n);
static IEnumerable<int> RRep(int n) => Enumerable.Range(0, n).Reverse();
static T[] Enumerate<T>(int n, Func<int, T> f) {
var a = new T[n];
for (int i = 0; i < a.Length; ++i) a[i] = f(i);
return a;
}
static public void Swap<T>(ref T a, ref T b) { var tmp = a; a = b; b = tmp; }
}
}
#region main
static class Ex {
static public string AsString(this IEnumerable<char> ie) { return new string(ie.ToArray()); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") {
return string.Join(st, ie);
}
static public void Main() {
Console.SetOut(new Program.IO.Printer(Console.OpenStandardOutput()) { AutoFlush = false });
var solver = new Program.Solver();
solver.Solve();
Console.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO {
using System.IO;
using System.Text;
using System.Globalization;
public class Printer : StreamWriter {
public override IFormatProvider FormatProvider => CultureInfo.InvariantCulture;
public Printer(Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
}
public class StreamScanner {
public StreamScanner(Stream stream) { str = stream; }
public readonly Stream str;
private readonly byte[] buf = new byte[1024];
private int len, ptr;
public bool isEof = false;
private byte read() {
if (isEof) return 0;
if (ptr >= len) {
ptr = 0;
if ((len = str.Read(buf, 0, 1024)) <= 0) {
isEof = true;
return 0;
}
}
return buf[ptr++];
}
public char Char() {
byte b = 0;
do b = read(); while ((b < 33 || 126 < b) && !isEof);
return (char)b;
}
public string Scan() {
var sb = new StringBuilder();
for (var b = Char(); b >= 33 && b <= 126; b = (char)read()) sb.Append(b);
return sb.ToString();
}
public string ScanLine() {
var sb = new StringBuilder();
for (var b = Char(); b != '\n' && b != 0; b = (char)read()) if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long() { return isEof ? long.MinValue : long.Parse(Scan()); }
public int Integer() { return isEof ? int.MinValue : int.Parse(Scan()); }
public double Double() { return isEof ? double.NaN : double.Parse(Scan(), CultureInfo.InvariantCulture); }
}
}
#endregion
#region FenwickTree
public class FenwickTree {
int n;
Number[] bit;
int max = 1;
public FenwickTree(int size) {
n = size; bit = new Number[n + 1];
while ((max << 1) <= n) max <<= 1;
}
/// <summary>sum[a,b]</summary>
public Number this[int i, int j] { get { return this[j] - this[i - 1]; } }
/// <summary>sum[0,i]</summary>
public Number this[int i] { get { Number s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } }
public int LowerBound(Number w) {
if (w <= 0) return 0;
int x = 0;
for (int k = max; k > 0; k >>= 1)
if (x + k <= n && bit[x + k] < w) {
w -= bit[x + k];
x += k;
}
return x + 1;
}
/// <summary>add v to bit[i]</summary>
public void Add(int i, Number v) {
Debug.Assert(i >= 1);
for (; i <= n; i += i & -i) bit[i] += v;
}
public Number[] Items {
get {
var ret = new Number[n + 1];
for (int i = 0; i < ret.Length; i++)
ret[i] = this[i, i];
return ret;
}
}
}
#endregion