結果
問題 | No.230 Splarraay スプラレェーイ |
ユーザー |
![]() |
提出日時 | 2015-06-19 23:14:50 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 1,602 ms / 5,000 ms |
コード長 | 4,931 bytes |
コンパイル時間 | 1,920 ms |
コンパイル使用メモリ | 114,252 KB |
実行使用メモリ | 27,520 KB |
最終ジャッジ日時 | 2024-07-07 04:16:12 |
合計ジャッジ時間 | 9,018 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 17 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.IO;using System.Linq;using System.Text;using System.Collections.Generic;using System.Diagnostics;using System.Numerics;using Enu = System.Linq.Enumerable;class Program{public void Solve(){int N = Reader.Int(), Q = Reader.Int();var Qs = Reader.IntTable(Q);long[] A = new long[N / BitW + 1];long[] B = new long[N / BitW + 1];long scoreA = 0, scoreB = 0;foreach (var q in Qs){if (q[0] == 0){long countA = Count(A, q[1], q[2]);long countB = Count(B, q[1], q[2]);if (countA > countB) scoreA += countA;if (countB > countA) scoreB += countB;}else if (q[0] == 1){RangeOr(A, q[1], q[2]);RangeClear(B, q[1], q[2]);//Console.WriteLine("A:" + Count(A, 0, N - 1) + " B:" + Count(B, 0, N - 1));}else{RangeOr(B, q[1], q[2]);RangeClear(A, q[1], q[2]);//Console.WriteLine("A:" + Count(A, 0, N - 1) + " B:" + Count(B, 0, N - 1));}}scoreA += Count(A, 0, N - 1);scoreB += Count(B, 0, N - 1);Console.WriteLine(scoreA + " " + scoreB);Console.ReadLine();}static readonly int BitW = 64;void RangeOr(long[] A, int from, int to){int fromI = from / BitW;int toI = to / BitW;for (int i = 0; i < BitW; i++)if (fromI * BitW + i >= from && fromI * BitW + i <= to)A[fromI] |= 1L << i;for (int i = fromI + 1; i < toI; i++)A[i] |= -1L;for (int i = 0; i < BitW; i++)if (toI * BitW + i >= from && toI * BitW + i <= to)A[toI] |= 1L << i;}void RangeClear(long[] A, int from, int to){int fromI = from / BitW;int toI = to / BitW;for (int i = 0; i < BitW; i++)if (fromI * BitW + i >= from && fromI * BitW + i <= to)A[fromI] &= ~(1L << i);for (int i = fromI + 1; i < toI; i++)A[i] = 0;for (int i = 0; i < BitW; i++)if (toI * BitW + i >= from && toI * BitW + i <= to)A[toI] &= ~(1L << i);}long Count(long[] A, int from, int to){int fromI = from / BitW;int toI = to / BitW;long count = 0;for (int i = 0; i < BitW; i++)if (fromI * BitW + i >= from && fromI * BitW + i <= to)count += A[fromI] >> i & 1;for (int i = fromI + 1; i < toI; i++)count += BitCount64(A[i]);if (toI != fromI)for (int i = 0; i < BitW; i++)if (toI * BitW + i >= from && toI * BitW + i <= to)count += A[toI] >> i & 1;return count;}static int BitCount64(long x){x -= x >> 1 & 0x5555555555555555;x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333);return (int)((x + (x >> 4) & 0x0f0f0f0f0f0f0f0f) * 0x0101010101010101 >> 56);}}class Entry { static void Main() { new Program().Solve(); } }class Reader{private static TextReader reader = Console.In;private static readonly char[] separator = { ' ' };private static readonly StringSplitOptions op = StringSplitOptions.RemoveEmptyEntries;private static string[] A = new string[0];private static int i;private static void Init() { A = new string[0]; }public static void Set(TextReader r) { reader = r; Init(); }public static void Set(string file) { reader = new StreamReader(file); Init(); }public static bool HasNext() { return CheckNext(); }public static string String() { return Next(); }public static int Int() { return int.Parse(Next()); }public static long Long() { return long.Parse(Next()); }public static double Double() { return double.Parse(Next()); }public static int[] IntLine() { return Array.ConvertAll(Split(Line()), int.Parse); }public static int[] IntArray(int N) { return Enu.Range(0, N).Select(i => Int()).ToArray(); }public static int[][] IntTable(int H) { return Enu.Range(0, H).Select(i => IntLine()).ToArray(); }public static string[] StringArray(int N) { return Enu.Range(0, N).Select(i => Line()).ToArray(); }public static string Line() { return reader.ReadLine().Trim(); }private static string[] Split(string s) { return s.Split(separator, op); }private static string Next() { CheckNext(); return A[i++]; }private static bool CheckNext(){if (i < A.Length) return true;string line = reader.ReadLine();if (line == null) return false;if (line == "") return CheckNext();A = Split(line);i = 0;return true;}}