ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1028. Звёзды

e.neverme Why got crash on Test3? [2] // Задача 1028. Звёзды 17 апр 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();
        }
    }
}
e.neverme Re: Why got crash on Test3? // Задача 1028. Звёзды 17 апр 2009 12:06
I see, there's a MLE prob...
gvsmirnov Re: Why got crash on Test3? // Задача 1028. Звёзды 18 сен 2009 21:35
You're trying to allocate over 200 MB, dude