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

Обсуждение задачи 1896. Военные учения 2.1

range tree
Послано lxn 9 июн 2016 16:15
Is there a solution without randge tree structure?
Re: range tree
Послано Shen Yang 23 авг 2016 17:26
I use Fenwick Tree get AC,0.452 seconds
Re: range tree
Послано xurshid_n 17 янв 2017 16:33
There possible segment tree with uint16_t for indexes greater than 2^15, and uin32_t for less 2^15. (two arrays:  uint16_t tree[N+N]; and uint32_t rem[32768] )
But I got WA38 ((
Re: range tree
Послано xurshid_n 17 янв 2017 20:57
I Got AC with segment tree!! uraaaaa.
Re: range tree
Послано Mahilewets 9 июл 2017 21:42
I can't do that.  C/C++.
I am using two cycles.
One to set up Fenwick tree and one to calculate the  answer.
Probably you are avoiding the use of the set up cycle somewhat.
I tested my solution on war games 2 and have got 93 ms.

UPD: got 46 ms on version 1

Edited by author 09.07.2017 22:20
Re: range tree
Послано Mahilewets 9 июл 2017 22:39
Finally,  I understood how to get rid of initialization cycle. Still TLE the same test 37.
Re: range tree
Послано Mahilewets 9 июл 2017 22:47
http://ideone.com/cUMY7U
I have no idea what can be optimized.
Re: range tree
Послано Mahilewets 9 июл 2017 22:57
Maybe bitwise operations are faster with UNSIGNED integers...
Re: range tree
Послано Mahilewets 10 июл 2017 13:24
So,  I tried to not calculate cnt=n-i+1 every iteration,  made while (1) cycle,  not call decrement on  Fenwick tree after last soldier.
TLE#37.
Re: range tree
Послано Mahilewets 6 авг 2017 15:09
My mistake was

I was using queries for O(log(N) *log(N))  time in Fenwick tree

But for that task,  there are suitable queries in just O(log(N))
Re: range tree
Послано Felix_Mate 27 фев 2018 21:41
You can use segment tree where vertex is segment with length=4.

1 2 3 4 5 6 7 8 9 10 => [1,2,3,4] [5,6,7,8] [9,10,11,12]

Memory is N*sizeof(int)+N*sizeof(bool)
Complexity is N*log(N/4)*4+N*log(N/4)
Re: range tree
Послано 🙂 Nayami_[PermSU] 22 ноя 2021 01:13
decomposition also works here, i've chosen amount of block about 300