fork(2) 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. 		add.Add(0);
  15. 	}
  16.  
  17. 	public int Pop()
  18. 	{
  19. 		int i = data.Count - 1;
  20. 		int res = data[i] + (inc += add[i]);
  21.  
  22. 		add.RemoveAt(i);
  23. 		data.RemoveAt(i);
  24.  
  25. 		return res;
  26. 	}
  27.  
  28. 	public void Inc(int r, int delta)
  29. 	{
  30. 		if (r < add.Count)
  31. 			add[r] += delta;
  32. 		else
  33. 			inc += delta;
  34. 	}
  35. }
  36.  
  37. public class Test
  38. {
  39. 	public static void Main()
  40. 	{
  41. 		 var watch = new Stopwatch();
  42. 		 var stack = new StackClass();
  43.  
  44. 		 var count = 100000001;
  45.  
  46. 		 watch.Start();
  47. 		 for (int i = 0; i < count; i++)
  48. 		 {
  49. 		     stack.Push(i);
  50. 		 }
  51. 		 Console.WriteLine(watch.Elapsed);
  52. 		 watch.Restart();
  53.  
  54. 		 for (int i = 0; i < count; i++)
  55. 		 {
  56. 		     stack.Inc(i, 2);
  57. 		 }
  58. 		 Console.WriteLine(watch.Elapsed);
  59. 		 watch.Restart();
  60.  
  61. 		 for (int i = 0; i < count; i++)
  62. 		 {
  63. 		     stack.Pop();
  64. 		 }
  65. 		 Console.WriteLine(watch.Elapsed);
  66. 	}
  67. }
Success #stdin #stdout 4.67s 29808KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
00:00:01.3654668
00:00:01.1821722
00:00:02.0888570
https://ideone.com/16JZ5V
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!