fork(1) download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Diagnostics;
  4.  
  5. public class StackClass
  6. {
  7.     private List<int> data = new List<int>(100000001);
  8.     private List<int> add = new List<int>(100000001);
  9.     private int inc = 0;
  10.  
  11.     public void Push(int x)
  12.     {
  13.         data.Add(x);
  14.         if (add.Count > 0) add[add.Count-1] += inc;
  15.         add.Add(0);
  16.         inc = 0;
  17.     }
  18.  
  19.     public int Pop()
  20.     {
  21.         int i = data.Count - 1;
  22.         int res = data[i] + (inc += add[i]);
  23.  
  24.         add.RemoveAt(i);
  25.         data.RemoveAt(i);
  26.  
  27.         return res;
  28.     }
  29.  
  30.     public void Inc(int r, int delta)
  31.     {
  32.         if (r < add.Count)
  33.             add[r] += delta;
  34.         else
  35.             inc += delta;
  36.     }
  37. }
  38.  
  39. public class Test
  40. {
  41. 	public static void Main()
  42. 	{
  43. 		 var watch = new Stopwatch();
  44. 		 var stack = new StackClass();
  45.  
  46. 		 var count = 100000001;
  47.  
  48. 		 watch.Start();
  49. 		 for (int i = 0; i < count; i++)
  50. 		 {
  51. 		     stack.Push(i);
  52. 		 }
  53. 		 Console.WriteLine(watch.Elapsed);
  54. 		 watch.Restart();
  55.  
  56. 		 for (int i = 0; i < count; i++)
  57. 		 {
  58. 		     stack.Inc(i, 2);
  59. 		 }
  60. 		 Console.WriteLine(watch.Elapsed);
  61. 		 watch.Restart();
  62.  
  63. 		 for (int i = 0; i < count; i++)
  64. 		 {
  65. 		     stack.Pop();
  66. 		 }
  67. 		 Console.WriteLine(watch.Elapsed);
  68. 	}
  69. }
Time limit exceeded #stdin #stdout 5s 29800KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
00:00:02.2248518
00:00:01.1903442
00:00:02.0052423
https://ideone.com/QTmDnz
language:
C# (gmcs 5.20.1)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!