ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1028. Stars

Why got crash on Test3?
Posted by e.neverme 17 Apr 2009 11:52
Here's my code, I see nowhere that could cause a crash...

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Ural {
    /// <summary>
    /// Stars
    /// Use binary indexed tree
    /// </summary>
    public class Prob1028 {
        private int N, MAX_X=0, MAX_Y=0;
        private int[,] map;
        private int[] level;
        private List<int> stars = new List<int>();

        public void ParseInput() {
            this.N = Int32.Parse(Console.ReadLine());

            for (int i = 0; i < N; i++) {
                string[] tokens = Console.ReadLine().Split(new char[] { ' ', '\t' }, StringSplitOptions.RemoveEmptyEntries);
                int a = Int32.Parse(tokens[0])+1;
                int b = Int32.Parse(tokens[1])+1;
                if (a > MAX_X) MAX_X = a;
                if (b > MAX_Y) MAX_Y = b;
                stars.Add(a);
                stars.Add(b);
            }

            this.map = new int[MAX_X + 1, MAX_Y + 1];
            this.level = new int[N];
        }

        public void Run() {
            for (int i = 0; i < N * 2; i += 2) {
                update(stars[i], stars[i + 1], 1);
            }
            for (int i = 0; i < N * 2; i += 2) {
                int l = read(stars[i], stars[i + 1]);
                level[l]++;
            }

            for (int i = 0; i < N; i++) {
                Console.WriteLine(level[i]);
            }
        }

        private void update(int x, int y, int val) {
            int y1;
            while (x <= MAX_X) {
                y1 = y;
                while (y1 <= MAX_Y) {
                    map[x, y1] += val;
                    y1 += (y1 & -y1);
                }
                x += (x & -x);
            }
        }

        private int read(int x, int y) {
            int sum = 0;
            int y1;
            while (x > 0) {
                y1 = y;
                while (y1 > 0) {
                    sum += map[x, y1];
                    y1 -= (y1 & -y1);
                }
                x -= (x & -x);
            }
            return sum - 1; // minus the point itself
        }

        public void Go() {
            ParseInput();
            Run();
        }

        static void Main(string[] args) {
            new Prob1028().Go();
        }
    }
}
Re: Why got crash on Test3?
Posted by e.neverme 17 Apr 2009 12:06
I see, there's a MLE prob...
Re: Why got crash on Test3?
Posted by gvsmirnov 18 Sep 2009 21:35
You're trying to allocate over 200 MB, dude