結果
| 問題 |
No.259 セグメントフィッシング＋
|
| コンテスト | |
| ユーザー |
 紙ぺーぱー
|
| 提出日時 | 2015-11-09 02:13:02 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 24,930 bytes |
| コンパイル時間 | 1,135 ms |
| コンパイル使用メモリ | 112,512 KB |
| 実行使用メモリ | 170,752 KB |
| 最終ジャッジ日時 | 2024-09-13 14:12:50 |
| 合計ジャッジ時間 | 9,605 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 9 WA * 1 TLE * 1 -- * 12 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;
using System.Linq;
using System.Diagnostics;
using System.Collections.Generic;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
using System.Numerics;
using Number = System.Int32;
using DataStructure;
namespace Program
{
public class Solver
{
public void Solve()
{
var n = sc.Integer();
var q = sc.Integer();
var a = new long[n];
var left = AVLTree.Build(a, 0, n);
var right = AVLTree.Build(a, 0, n);
var last = 0;
for (int _ = 0; _ < q; _++)
{
//Debug.WriteLine(_);
//AVLTree.walk(left, null);
//AVLTree.walk(right, null);
var c = sc.Char();
var t = sc.Integer();
var dt = (t - last) % (2 * n);
var x = sc.Integer();
var y = sc.Integer();
if (dt <= n)
{
var rl1 = left.Split(dt);
var rl2 = right.Split(n - dt);
left = AVLTree.Merge(rl1.rst, rl2.rst.Reverse(0, rl2.rst.cnt));
right = AVLTree.Merge(rl1.lst.Reverse(0, rl1.lst.cnt), rl2.lst);
}
else
{
dt -= n;
var rl1 = left.Split(dt);
var rl2 = right.Split(n - dt);
left = AVLTree.Merge(rl2.lst.Reverse(0, rl2.lst.cnt), rl1.lst);
right = AVLTree.Merge(rl2.rst, rl1.rst.Reverse(0, rl1.rst.cnt));
}
if (c == 'L')
left.AddValue(x, x + 1, y);
else if (c == 'R')
right.AddValue(x, x + 1, y);
else
{
var l = left.Query(x, y);
var r = right.Query(x, y);
IO.Printer.Out.WriteLine(l + r);
}
last = t;
}
//AVLTree.walk(left, null);
//AVLTree.walk(right, null);
}
public IO.StreamScanner sc = new IO.StreamScanner(Console.OpenStandardInput());
static T[] Enumerate<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; }
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(System.Linq.Enumerable.ToArray(ie)); }
static public string AsJoinedString<T>(this IEnumerable<T> ie, string st = " ") { return string.Join(st, ie); }
static public void Main()
{
var solver = new Program.Solver();
solver.Solve();
Program.IO.Printer.Out.Flush();
}
}
#endregion
#region Ex
namespace Program.IO
{
using System.IO;
using System.Text;
using System.Globalization;
public class Printer : StreamWriter
{
static Printer() { Out = new Printer(Console.OpenStandardOutput()) { AutoFlush = false }; }
public static Printer Out { get; set; }
public override IFormatProvider FormatProvider { get { return CultureInfo.InvariantCulture; } }
public Printer(System.IO.Stream stream) : base(stream, new UTF8Encoding(false, true)) { }
public Printer(System.IO.Stream stream, Encoding encoding) : base(stream, encoding) { }
public void Write<T>(string format, T[] source) { base.Write(format, source.OfType<object>().ToArray()); }
public void WriteLine<T>(string format, T[] source) { base.WriteLine(format, source.OfType<object>().ToArray()); }
}
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;
public bool IsEndOfStream { get { return isEof; } }
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 = (char)read())
if (b == 0) break;
else if (b != '\r') sb.Append(b);
return sb.ToString();
}
public long Long()
{
if (isEof) return long.MinValue;
long ret = 0; byte b = 0; var ng = false;
do b = read();
while (b != '-' && (b < '0' || '9' < b));
if (b == '-') { ng = true; b = read(); }
for (; true; b = read())
{
if (b < '0' || '9' < b)
return ng ? -ret : ret;
else ret = ret * 10 + b - '0';
}
}
public int Integer() { return (isEof) ? int.MinValue : (int)Long(); }
public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
private T[] enumerate<T>(int n, Func<T> f)
{
var a = new T[n];
for (int i = 0; i < n; ++i) a[i] = f();
return a;
}
public char[] Char(int n) { return enumerate(n, Char); }
public string[] Scan(int n) { return enumerate(n, Scan); }
public double[] Double(int n) { return enumerate(n, Double); }
public int[] Integer(int n) { return enumerate(n, Integer); }
public long[] Long(int n) { return enumerate(n, Long); }
}
}
#endregion
#region RBSTNode
public class RBSTNode
{
public long val;
public RBSTNode lst, rst;
public int cnt;
public long add;
public long sum;
public bool rev;
public RBSTNode(long v) { val = v; RBST.Update(this); }
public RBSTNode(RBSTNode l, RBSTNode r) { lst = l; rst = r; }
public override string ToString()
{
return string.Format("cnt:{0}, val:{1}, add:{2}, sum:{3}, rev:{4}", cnt, val, add, sum, rev);
}
}
static public class RBST
{
static void Swap(ref RBSTNode l, ref RBSTNode r) { var tmp = l; l = r; r = tmp; }
/// <summary>
/// long配列aの[b,e)から木を構築
/// </summary>
static public RBSTNode Build(long[] a, int b, int e)
{
var n = e - b;
if (n == 0) return null;
var m = b + (n >> 1);
var l = Build(a, b, m);
var r = Build(a, m + 1, e);
var ret = new RBSTNode(a[m]) { lst = l, rst = r };
return Update(ret);
}
/// <summary>
/// 木を配列にコピーする．
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
static public long[] ToArray(this RBSTNode n)
{
var a = new long[Count(n)];
CopyTo(n, a, 0, 0);
return a;
}
static int CopyTo(RBSTNode n, long[] a, int it, long add)
{
if (n == null)
return it;
add += n.add;
if (n.rev)
Reverse(n);
it = CopyTo(n.lst, a, it, add);
a[it++] = n.val + add;
it = CopyTo(n.rst, a, it, add);
return it;
}
/// <summary>
/// ノードの部分木のサイズを取得
/// </summary>
static public int Count(this RBSTNode n) { return n == null ? 0 : n.cnt; }
/// <summary>
/// 区間[l,r)の総和を取得
/// </summary>
static public long Query(this RBSTNode n, int l, int r)
{
if (n == null || r <= 0 || Count(n) <= l) return 0;
if (l <= 0 && Count(n) <= r)
return n.sum;
long ret = 0;
n = FallDown(n);
if (0 < r && l < Count(n.lst)) ret += Query(n.lst, l, r);
if (Count(n.lst) + 1 < r && l < Count(n)) ret += Query(n.rst, l - Count(n.lst) - 1, r - Count(n.lst) - 1);
if (l <= Count(n.lst) && Count(n.lst) < r) ret += n.val;
//ret += n.add * (Math.Min(r, Count(n)) - Math.Max(l, 0));
return ret;
}
static void Reverse(RBSTNode n)
{
if (n == null) return;
Swap(ref n.lst, ref n.rst);
n.rev = false;
if (n.lst != null) n.lst.rev = !n.lst.rev;
if (n.rst != null) n.rst.rev = !n.rst.rev;
}
/// <summary>
/// ノードの値の更新
/// </summary>
static public RBSTNode Update(this RBSTNode n)
{
if (n == null) return null;
n.cnt = 1;
if (n.lst != null) n.cnt += n.lst.cnt;
if (n.rst != null) n.cnt += n.rst.cnt;
n.sum = n.val + Count(n) * n.add;
if (n.lst != null) n.sum += n.lst.sum;
if (n.rst != null) n.sum += n.rst.sum;
return n;
}
/// <summary>
/// 区間[l,r)にvを加算．
/// </summary>
static public RBSTNode AddValue(this RBSTNode n, int l, int r, long v)
{
if (n == null || r <= 0 || Count(n) <= l) return n;
FallDown(n);
if (l <= 0 && Count(n) <= r)
{
n.add += v;
return Update(n);
}
else
{
if (0 < r && l < Count(n.lst))
n.lst = AddValue(n.lst, l, r, v);
if (Count(n.lst) + 1 < r && l < Count(n))
n.rst = AddValue(n.rst, l - Count(n.lst) - 1, r - Count(n.lst) - 1, v);
if (l <= Count(n.lst) && Count(n.lst) < r)
n.val += v;
return Update(n);
}
}
/// <summary>
/// 区間[l,r)を反転．
/// </summary>
static public RBSTNode Reverse(this RBSTNode n, int l, int r)
{
if (n == null || r <= 0 || Count(n) <= l) return n;
FallDown(n);
var lmr = Split(n, l, r);
lmr[1].rev = !lmr[1].rev;
return Merge(lmr[0], lmr[1], lmr[2]);
}
/// <summary>
/// 0-indexedでk番目のノードを取得
/// </summary>
static public RBSTNode GetNode(this RBSTNode n, int k)
{
while (n != null)
{
n = FallDown(n);
if (k < Count(n.lst))
n = n.lst;
else if (k == Count(n.lst))
break;
else
{
k -= Count(n.lst) + 1;
n = n.rst;
}
}
return n;
}
static RBSTNode FallDown(RBSTNode n)
{
if (n == null) return null;
if (n.rev)
Reverse(n);
if (n.add == 0) return n;
if (n.lst != null)
{
n.lst.add += n.add;
Update(n.lst);
}
if (n.rst != null)
{
n.rst.add += n.add;
Update(n.rst);
}
n.val += n.add;
n.add = 0;
return Update(n);
}
static Random rand = new Random();
static public RBSTNode Merge(RBSTNode a, RBSTNode b)
{
if (a == null || b == null)
return a ?? b;
if (rand.Next() % (Count(a) + Count(b)) < Count(a))
{
a = FallDown(a);
a.rst = Merge(a.rst, b);
return Update(a);
}
else
{
b = FallDown(b);
b.lst = Merge(a, b.lst);
return Update(b);
}
}
static public RBSTNode Merge(RBSTNode l, RBSTNode m, RBSTNode r)
{
return Merge(Merge(l, m), r);
}
static public RBSTNode Split(this RBSTNode n, int k)
{
if (n == null) return new RBSTNode(null, null);
n = FallDown(n);
if (k <= Count(n.lst))
{
var s = Split(n.lst, k);
n.lst = s.rst;
s.rst = Update(n);
return s;
}
else
{
var s = Split(n.rst, k - Count(n.lst) - 1);
n.rst = s.lst;
s.lst = Update(n);
return s;
}
}
static public RBSTNode[] Split(RBSTNode n, int l, int r)
{
var p1 = RBST.Split(n, r);
var q1 = RBST.Split(p1.lst, l);
return new RBSTNode[] { q1.lst, q1.rst, p1.rst };
}
static public RBSTNode Insert(this RBSTNode n, int k, RBSTNode item)
{
if (n == null) return item;
n = FallDown(n);
if (rand.Next() % (Count(n) + Count(item)) < Count(n))
{
if (k <= Count(n.lst))
n.lst = Insert(n.lst, k, item);
else n.rst = Insert(n.rst, k - Count(n.lst) - 1, item);
return Update(n);
}
else
{
var s = Split(n, k);
item.lst = s.lst; item.rst = s.rst;
return Update(item);
}
}
static public RBSTNode RemoveAt(this RBSTNode n, int k)
{
if (n == null) return null;
n = FallDown(n);
if (k < Count(n.lst))
{
n.lst = RemoveAt(n.lst, k);
return Update(n);
}
else if (k == Count(n.lst))
{
var nn = Merge(n.lst, n.rst);
Isolate(n);
return nn;
}
else
{
n.rst = RemoveAt(n.rst, k - Count(n.rst) - 1);
return Update(n);
}
}
static public RBSTNode Isolate(RBSTNode n)
{
if (n == null) return null;
n.lst = n.rst = null;
return Update(n);
}
}
#endregion
namespace DataStructure
{
using Number = Int64;
public class AVLNode
{
public Number key;
public Number sum, add;
public bool rev;
public int cnt, height;
public AVLNode lst, rst;
static readonly public AVLNode NIL = new AVLNode();
static AVLNode()
{
NIL.lst = NIL.rst = NIL;
}
public AVLNode()
{
}
public AVLNode(Number k)
{
key = k;
sum = key;
cnt = 1;
height = 1;
lst = rst = NIL;
}
public AVLNode Update()
{
if (this == NIL) return this;
cnt = 1 + lst.cnt + rst.cnt;
height = Math.Max(lst.height, rst.height) + 1;
//optional
sum = key + add * cnt + lst.sum + rst.sum;
return this;
}
public AVLNode this[int k]
{
get
{
if (k == lst.cnt) return this;
else if (k < lst.cnt) return lst[k];
else return rst[k - (lst.cnt + 1)];
}
}
public int UpperBound(Number k)
{
if (cnt == 0) return 0;
if (key <= k) return lst.cnt + 1 + rst.UpperBound(k);
else return lst.UpperBound(k);
}
public int LowerBound(Number k)
{
if (cnt == 0) return 0;
if (k <= key) return lst.LowerBound(k);
else return lst.cnt + 1 + rst.LowerBound(k);
}
public int EqualRange(Number k)
{
return UpperBound(k) - LowerBound(k);
}
override public string ToString()
{
if (this == NIL) return "nil";
return string.Format("k={0} cnt={1}", key, cnt);
}
}
static public class AVLTree
{
static private AVLNode RotR(this AVLNode n)
{
var l = n.lst;
n.lst = l.rst;
l.rst = n;
n.Update();
l.Update();
return l;
}
static private AVLNode RotL(this AVLNode n)
{
var r = n.rst;
n.rst = r.lst;
r.lst = n;
n.Update();
r.Update();
return r;
}
static public AVLNode Build(Number[] a, int b, int e)
{
var n = e - b;
if (n == 0) return AVLNode.NIL;
var m = b + (n >> 1);
var l = Build(a, b, m);
var r = Build(a, m + 1, e);
var ret = new AVLNode(a[m]) { lst = l, rst = r };
return ret.Update();
}
static public Number Query(this AVLNode n, int l, int r)
{
if (n == null || r <= 0 || n.cnt <= l) return 0;
if (l <= 0 && n.cnt <= r)
return n.sum;
Number ret = 0;
FallDown(n);
if (0 < r && l < n.lst.cnt) ret += Query(n.lst, l, r);
if (n.lst.cnt + 1 < r && l < n.cnt) ret += Query(n.rst, l - n.lst.cnt - 1, r - n.lst.cnt - 1);
if (l <= n.lst.cnt && n.lst.cnt < r) ret += n.key;
return ret;
}
static public AVLNode AddValue(this AVLNode n, int l, int r, Number v)
{
if (n == AVLNode.NIL || r <= 0 || n.cnt <= l) return n;
FallDown(n);
if (l <= 0 && n.cnt <= r)
{
n.add += v;
return n.Update();
}
else
{
if (0 < r && l < n.lst.cnt)
n.lst = AddValue(n.lst, l, r, v);
if (n.lst.cnt + 1 < r && l < n.cnt)
n.rst = AddValue(n.rst, l - n.lst.cnt - 1, r - n.lst.cnt - 1, v);
if (l <= n.lst.cnt && n.lst.cnt < r)
n.key += v;
return n.Update();
}
}
static void Swap(ref AVLNode l, ref AVLNode r) { var tmp = l; l = r; r = tmp; }
static void reverse(AVLNode n)
{
if (n == AVLNode.NIL) return;
Swap(ref n.lst, ref n.rst);
n.rev = false;
if (n.lst != AVLNode.NIL) n.lst.rev = !n.lst.rev;
if (n.rst != AVLNode.NIL) n.rst.rev = !n.rst.rev;
}
static public AVLNode Reverse(this AVLNode n, int l, int r)
{
if (n == AVLNode.NIL || r <= 0 || n.cnt <= l) return n;
FallDown(n);
var lmr = Split(n, l, r);
lmr[1].rev = !lmr[1].rev;
return Merge(lmr[0], lmr[1], lmr[2]);
}
static AVLNode FallDown(AVLNode n)
{
if (n == AVLNode.NIL) return n;
if (n.rev)
reverse(n);
if (n.add == 0) return n;
if (n.lst != AVLNode.NIL)
{
n.lst.add += n.add;
n.lst.Update();
}
if (n.rst != AVLNode.NIL)
{
n.rst.add += n.add;
n.rst.Update();
}
n.key += n.add;
n.add = 0;
return n.Update();
}
static public AVLNode Add(this AVLNode tree, Number k)
{
return Insert(tree, new AVLNode(k), tree.LowerBound(k));
}
static public AVLNode Remove(this AVLNode tree, Number k)
{
return RemoveAt(tree, tree.LowerBound(k));
}
static public AVLNode Insert(this AVLNode tree, AVLNode n, int k)
{
if (tree == AVLNode.NIL) return n;
FallDown(tree);
var cnt = tree.lst.cnt;
if (k > cnt)
tree.rst = tree.rst.Insert(n, k - (cnt + 1));
else
tree.lst = tree.lst.Insert(n, k);
tree.Update();
var diff = tree.lst.height - tree.rst.height;
if (diff == 2)
{
tree.lst = FallDown(tree.lst);
if (tree.lst.rst.height - tree.lst.lst.height == 1) tree.lst = tree.lst.RotL();
tree = tree.RotR();
}
if (diff == -2)
{
tree.rst = FallDown(tree.rst);
if (tree.rst.lst.height - tree.rst.rst.height == 1) tree.rst = tree.rst.RotR();
tree = tree.RotL();
}
return tree;
}
static private AVLNode remove(this AVLNode root, AVLNode tree)
{
FallDown(tree);
if (tree.rst == AVLNode.NIL)
{
root.key = tree.key;
return tree.lst;
}
tree.rst = remove(root, tree.rst);
tree.Update();
var diff = tree.lst.height - tree.rst.height;
if (diff == 2)
{
if (tree.lst.rst.height - tree.lst.lst.height == 1)
tree.lst = tree.lst.RotL();
tree = tree.RotR();
}
if (diff == -2)
{
if (tree.rst.lst.height - tree.rst.rst.height == 1)
tree.rst = tree.rst.RotR();
tree = tree.RotL();
}
return tree;
}
static public AVLNode RemoveAt(this AVLNode tree, int k)
{
if (tree == AVLNode.NIL) return tree;
var cnt = tree.lst.cnt;
FallDown(tree);
if (k > cnt)
tree.rst = tree.rst.RemoveAt(k - (cnt + 1));
else if (k == cnt)
{
if (tree.lst == AVLNode.NIL)
tree = tree.rst;
else if (tree.rst == AVLNode.NIL) tree = tree.lst;
else tree.lst = remove(tree, tree.lst);
}
else tree.lst = tree.lst.RemoveAt(k);
tree.Update();
var diff = tree.lst.height - tree.rst.height;
if (diff == 2)
{
if (tree.lst.rst.height - tree.lst.lst.height == 1) tree.lst = tree.lst.RotL();
tree = tree.RotR();
}
if (diff == -2)
{
if (tree.rst.lst.height - tree.rst.rst.height == 1) tree.rst = tree.rst.RotR();
tree = tree.RotL();
}
return tree;
}
static public AVLNode merge(AVLNode l, AVLNode t, AVLNode r)
{
AVLNode tree;
if (l.height > r.height)
{
FallDown(l);
l.rst = merge(l.rst, t, r);
tree = l;
}
else if (l.height == r.height)
{
if (l == AVLNode.NIL)
return t.cnt == 0 ? l : t;
t.lst = l; t.rst = r;
if (t.cnt == 0)
t.lst = remove(t, t.lst);
tree = t;
}
else
{
FallDown(r);
r.lst = merge(l, t, r.lst);
tree = r;
}
tree.Update();
var diff = tree.lst.height - tree.rst.height;
if (diff == 2)
{
if (tree.lst.rst.height - tree.lst.lst.height == 1)
tree.lst = tree.lst.RotL();
tree = tree.RotR();
}
if (diff == -2)
{
if (tree.rst.lst.height - tree.rst.rst.height == 1)
tree.rst = tree.rst.RotR();
tree = tree.RotL();
}
if (Math.Abs(tree.lst.height - tree.rst.height) > 1) throw new Exception();
return tree;
}
static public AVLNode Merge(AVLNode l, AVLNode r)
{
return merge(l, new AVLNode(), r);
}
static public AVLNode Merge(AVLNode l, AVLNode m, AVLNode r)
{
return Merge(Merge(l, m), r);
}
static public int cnt = 0, wai = 0;
static public AVLNode Split(this AVLNode tree, int k)
{
if (tree == AVLNode.NIL) return new AVLNode() { lst = tree, rst = tree };
FallDown(tree);
if (k <= tree.lst.cnt)
{
var s = Split(tree.lst, k);
s.rst = merge(s.rst, new AVLNode(tree.key), tree.rst);
return s;
}
else
{
var s = Split(tree.rst, k - tree.lst.cnt - 1);
s.lst = merge(tree.lst, new AVLNode(tree.key), s.lst);
return s;
}
}
static public AVLNode[] Split(AVLNode n, int l, int r)
{
var p1 = n.Split(r);
var q1 = p1.lst.Split(l);
return new AVLNode[] { q1.lst, q1.rst, p1.rst };
}
static public string AsJoindString(this AVLNode tree)
{
var list = new List<Number>();
walk(tree, list);
return list.AsJoinedString();
}
static public void walk(this AVLNode tree, List<Number> ret)
{
if (tree == AVLNode.NIL) return;
walk(tree.lst, ret);
//ret.Add(tree.key);
if (Math.Abs(tree.lst.height - tree.rst.height) > 1) throw new Exception();
walk(tree.rst, ret);
}
}
}