結果
問題 | No.607 開通777年記念 |
ユーザー |
![]() |
提出日時 | 2017-12-07 00:25:04 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 176 ms / 2,000 ms |
コード長 | 13,843 bytes |
コンパイル時間 | 1,335 ms |
コンパイル使用メモリ | 117,504 KB |
実行使用メモリ | 18,432 KB |
最終ジャッジ日時 | 2024-11-29 01:36:47 |
合計ジャッジ時間 | 2,728 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections;using System.Collections.Generic;using System.Diagnostics;using System.IO;using System.Linq;using System.Numerics;using System.Text;using static System.Math;using static Extensions;using static MathExtensions;public static class Program{public static void Solve(){var (n, m) = (I, I);var bit = new FenwickTree<int>(n, Group.Sum_Int32);Repeat(m, () =>{Repeat(n, i => { bit[i] += I; });var head = 0;var last = 0;while (last < n){var sum = bit[head, last];if (sum == 777){Console.WriteLine("YES");Console.Out.Flush(); // !!!!!!!!!!!!!!Environment.Exit(0); // flushされずに終わってWAはひどい}if (sum > 777){if (head == last) last++;head++;}else last++;}});Console.WriteLine("NO");}#region Scannersstatic Scanner _scanner;static char C => _scanner.NextChar();static string S => _scanner.NextString();static int I => _scanner.NextInt();static long L => _scanner.NextLong();static BigInteger B => _scanner.NextBigInteger();static double D => _scanner.NextDouble();static decimal M => _scanner.NextDecimal();#endregionpublic static void Main(){var sw = new StreamWriter(Console.OpenStandardOutput());sw.NewLine = "\n";#if DEBUGsw.AutoFlush = true;//Console.SetError(sw);#elsesw.AutoFlush = false;#endifConsole.SetOut(sw);_scanner = new Scanner(Console.OpenStandardInput());Solve();Console.Out.Flush();}}public static partial class Extensions{}#region Librarypublic class Scanner{private readonly Stream _stream;private const int _bufferSize = 1024;private readonly byte[] _buf = new byte[_bufferSize];private int _len, _ptr;public Scanner(Stream stream){_stream = stream;}public byte ReadByte(){if (_ptr >= _len){_len = _stream.Read(_buf, 0, _bufferSize);_ptr = 0;}return _buf[_ptr++];}public char ReadChar() => (char)ReadByte();public string ReadLine(){var r = new StringBuilder();if (_ptr == 0) r.Append(ReadChar());for (; _ptr < _len; _ptr++) r.Append((char)_buf[_ptr]);return r.ToString();}public char NextChar() => char.Parse(NextString());public string NextString(){var r = new StringBuilder();var b = ReadChar();while (b != ' ' && b != '\n'){r.Append(b);b = ReadChar();}return r.ToString();}public int NextInt() => (int)NextLong();public long NextLong(){var r = 0L;var b = ReadByte();var n = b == '-';if (n) b = ReadByte();while (b != ' ' && b != '\n'){r = r * 10 + b - '0';b = ReadByte();}return n ? -r : r;}public BigInteger NextBigInteger(){var r = new BigInteger();var b = ReadByte();var n = b == '-';if (n) b = ReadByte();while (b != ' ' && b != '\n'){r = r * 10 + b - '0';b = ReadByte();}return n ? -r : r;}public double NextDouble(){var i = 0L;var b = ReadByte();var n = b == '-';if (n) b = ReadByte();while (b != '.' && b != ' ' && b != '\n'){i = i * 10 + b - '0';b = ReadByte();}if (b != '.') return n ? -i : i;b = ReadByte();var f = 0L;var p = 0;while (b != ' ' && b != '\n'){f = f * 10 + b - '0';b = ReadByte();p++;}var r = i + (double)f / MathExtensions.Pow(10, p);return n ? -r : r;}public decimal NextDecimal() => decimal.Parse(NextString());public T Next<T>(Converter<string, T> parser) => parser(NextString());}public class Monoid<T>{public Monoid(T unit, Func<T, T, T> append){this.Unit = unit;this.Append = append;}public T Unit { get; }public Func<T, T, T> Append { get; }}public static class Monoid{public static Monoid<T> Create<T>(T unit, Func<T, T, T> append) => new Monoid<T>(unit, append);public static readonly Monoid<int> Min_Int32 = new Monoid<int>(int.MaxValue, Min);public static readonly Monoid<int> Max_Int32 = new Monoid<int>(int.MinValue, Max);public static readonly Monoid<long> Min_Int64 = new Monoid<long>(long.MaxValue, Min);public static readonly Monoid<long> Max_Int64 = new Monoid<long>(long.MinValue, Max);}public class Group<T> : Monoid<T>{public Group(T unit, Func<T, T, T> append, Func<T, T> invert) : base(unit, append){this.Invert = invert;}public Func<T, T> Invert { get; }}public static class Group{public static Group<T> Create<T>(T unit, Func<T, T, T> append, Func<T, T> invert)=> new Group<T>(unit, append, invert);public static readonly Group<int> Sum_Int32 = new Group<int>(0, (x, y) => x + y, x => -x);public static readonly Group<long> Sum_Int64 = new Group<long>(0L, (x, y) => x + y, x => -x);}public class FenwickTree<T> : IReadOnlyList<T>{private readonly T[] _tree;public FenwickTree(int length, Monoid<T> monoid){_tree = Enumerable.Repeat(monoid.Unit, length + 1).ToArray();this.Monoid = monoid;}public FenwickTree(int length, Group<T> group) : this(length, (Monoid<T>)group){this.Group = group;}public FenwickTree(IEnumerable<T> collection, Monoid<T> monoid){var count = collection.Count();this.Monoid = monoid;_tree = new T[count + 1];collection.ForEach((x, i) => { _tree[i + 1] = x; });for (var i = 1; i < count; i++){var j = i + (i & -i);_tree[j] = monoid.Append(_tree[j], _tree[i]);}}public FenwickTree(IEnumerable<T> collection, Group<T> group) : this(collection, (Monoid<T>)group){this.Group = group;}public Monoid<T> Monoid { get; } // commutativepublic Group<T> Group { get; } // commutativepublic int Length => _tree.Length - 1;int IReadOnlyCollection<T>.Count => this.Length;public T this[int i]{get => this[i, i];set => this.Append(i, this.Group.Append(value, this.Group.Invert(this[i])));}public T this[int l, int r]{get{var acc = this.Group.Unit;r++;for (; r > l; r -= r & -r) acc = this.Group.Append(acc, _tree[r]);for (; l > r; l -= l & -l) acc = this.Group.Append(acc, this.Group.Invert(_tree[l]));return acc;}}public IEnumerator<T> GetEnumerator(){for (var i = 0; i < this.Length; i++) yield return Concat(i);}IEnumerator IEnumerable.GetEnumerator() => this.GetEnumerator();public T Concat(int l){var acc = this.Monoid.Unit;for (l++; l > 0; l -= l & -l) acc = this.Monoid.Append(acc, _tree[l]);return acc;}public void Append(int r, T value){for (r++; r <= this.Length; r += r & -r) _tree[r] = this.Monoid.Append(_tree[r], value);}}[DebuggerStepThrough]public static partial class Extensions{public static void Assert(bool condition){if (!condition) throw new Exception("Assertion failed");}public static string AsString(this IEnumerable<char> source) => new string(source.ToArray());public static void ForEach<T>(this IEnumerable<T> source, Action<T> action){foreach (var item in source) action(item);}public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, _> func){foreach (var item in source) func(item);}public static void ForEach<T>(this IEnumerable<T> source, Action<T, int> action){var i = 0;foreach (var item in source) action(item, i++);}public static void ForEach<T, _>(this IEnumerable<T> source, Func<T, int, _> func){var i = 0;foreach (var item in source) func(item, i++);}public static T Iterate<T>(int count, T seed, Func<T, T> func){var r = seed;for (var i = 0; i < count; i++) r = func(r);return r;}public static void Repeat(int count, Action action){for (var i = 0; i < count; i++) action();}public static void Repeat(int count, Action<int> action){for (var i = 0; i < count; i++) action(i);}public static IEnumerable<T> Repeat<T>(Func<T> func){for (var i = 0; ; i++) yield return func();}public static IEnumerable<T> Repeat<T>(int count, Func<T> func){for (var i = 0; i < count; i++) yield return func();}public static IEnumerable<T> Repeat<T>(Func<int, T> func){for (var i = 0; ; i++) yield return func(i);}public static IEnumerable<T> Repeat<T>(int count, Func<int, T> func){for (var i = 0; i < count; i++) yield return func(i);}public static void Swap<T>(ref T x, ref T y){var tmp = x; x = y; y = tmp;}public static (T1[], T2[]) Unzip<T1, T2>(this ICollection<(T1, T2)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var i = 0;foreach (var (t1, t2) in source) { ts1[i] = t1; ts2[i] = t2; i++; }return (ts1, ts2);}public static (T1[], T2[], T3[]) Unzip<T1, T2, T3>(this ICollection<(T1, T2, T3)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var ts3 = new T3[source.Count];var i = 0;foreach (var (t1, t2, t3) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; i++; }return (ts1, ts2, ts3);}public static (T1[], T2[], T3[], T4[]) Unzip<T1, T2, T3, T4>(this ICollection<(T1, T2, T3, T4)> source){var ts1 = new T1[source.Count];var ts2 = new T2[source.Count];var ts3 = new T3[source.Count];var ts4 = new T4[source.Count];var i = 0;foreach (var (t1, t2, t3, t4) in source) { ts1[i] = t1; ts2[i] = t2; ts3[i] = t3; ts4[i] = t4; i++; }return (ts1, ts2, ts3, ts4);}public static IEnumerable<T> Zip<T1, T2, T3, T>(this IEnumerable<T1> first, IEnumerable<T2> second, IEnumerable<T3> thrid, Func<T1, T2, T3, T>resultSelector){using (var e1 = first.GetEnumerator())using (var e2 = second.GetEnumerator())using (var e3 = thrid.GetEnumerator()){while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext())yield return resultSelector(e1.Current, e2.Current, e3.Current);}}public static IEnumerable<T> Zip<T1, T2, T3, T4, T>(this IEnumerable<T1> first, IEnumerable<T2> second, IEnumerable<T3> thrid, IEnumerable<T4>fourth, Func<T1, T2, T3, T4, T> resultSelector){using (var e1 = first.GetEnumerator())using (var e2 = second.GetEnumerator())using (var e3 = thrid.GetEnumerator())using (var e4 = fourth.GetEnumerator()){while (e1.MoveNext() && e2.MoveNext() && e3.MoveNext() && e4.MoveNext())yield return resultSelector(e1.Current, e2.Current, e3.Current, e4.Current);}}}[DebuggerStepThrough]public static class MathExtensions{public static int Gcd(int left, int right){int r;while ((r = left % right) != 0) { left = right; right = r; }return right;}public static long Gcd(long left, long right){long r;while ((r = left % right) != 0L) { left = right; right = r; }return right;}public static BigInteger Gcd(BigInteger left, BigInteger right)=> BigInteger.GreatestCommonDivisor(left, right);public static int HighestOneBit(int x){x |= x >> 01;x |= x >> 02;x |= x >> 04;x |= x >> 08;x |= x >> 16;return x - (x >> 1);}public static long HighestOneBit(long x){x |= x >> 01;x |= x >> 02;x |= x >> 04;x |= x >> 08;x |= x >> 16;x |= x >> 32;return x - (x >> 1);}public static int Lcm(int left, int right) => left / Gcd(left, right) * right;public static long Lcm(long left, long right) => left / Gcd(left, right) * right;public static BigInteger Lcm(BigInteger left, BigInteger right)=> left / Gcd(left, right) * right;public static int Pow(int value, int exponent){var r = 1;while (exponent > 0){if ((exponent & 1) == 1) r *= value;value *= value;exponent >>= 1;}return r;}public static long Pow(long value, int exponent){var r = 1L;while (exponent > 0){if ((exponent & 1) == 1) r *= value;value *= value;exponent >>= 1;}return r;}public static long Fact(int value){var r = 1L;for (var i = 2; i <= value; i++) r *= i;return r;}}#endregion