Show all threads Hide all threads Show all messages Hide all messages |
Hint | basuki | 1491. Unreal Story | 24 Apr 2022 11:50 | 2 |
Hint basuki 25 Mar 2019 08:32 Segment Tree/ Fenwick Tree with range update and point query Too expensive for this problem. You can just add c to some array[a] and add -c to array[b + 1]. So when you need to print the answer, you just do loop through all knights from 1 to n and firstly add value from array[i] to some variable, then print this variable. |
Why my program get WA #18 ? | WiN_uA | 1491. Unreal Story | 17 Feb 2022 02:44 | 3 |
#include <iostream> using namespace std; int main() { unsigned long long n,a,b,c,s; int i; unsigned long long x[100001]; memset(x,0,sizeof(x)); cin>>n; for (i=1;i<=n+1;i++) { cin>>a>>b>>c; x[a]=x[a]+c; x[b+1]=x[b+1]-c; };s=0; for (i=1;i<=n;i++) { s=s+x[i]; if (i==n) cout<<s<<endl; else cout<<s<<" "; } }; tried to make this code faster, but seems its imposible |
. | zxc master | 1491. Unreal Story | 8 Dec 2020 04:24 | 1 |
. zxc master 8 Dec 2020 04:24 . случайно Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 |
I solve this problem O(N) time 0.062 | Otabek Toshkanov | 1491. Unreal Story | 30 May 2018 19:08 | 1 |
This problem is very easy. I use idea similar dp. Edited by author 30.05.2018 19:11 |
TLE on test18 | VolkovStanislav[MSU_Tashkent] | 1491. Unreal Story | 24 Jul 2017 01:14 | 2 |
I use very simple algo, prompt other algo please. Edited by author 10.08.2011 15:32 Segment tree with range update, obviously. And even Fenwick tree with range increment. (Petr described such a Fenwick tree in his blog) |
The Correct Java Solution Got TLE 17! | Alexander Sokolov [MAI] | 1491. Unreal Story | 26 Aug 2010 15:50 | 5 |
[code deleted] Edited by author 20.10.2006 23:12 Edited by moderator 01.12.2019 21:13 The same algo on Pascal got AC in 0.156 sec Thank you Alexander, my algorithm AC 0.484 |
Problem is not clear | Alexander Samal | 1491. Unreal Story | 18 Apr 2010 12:43 | 2 |
Who can explain me: if N == 1, what numbers (a, b, c) the knight can say? You are right! N can not be equal to 1. Problem statement is updated. |
my program get AC 0.14 ! Best algorithm ! | Phan Hoài Nam - Đại học Ngoại ngữ Tin Học TP.HCM | 1491. Unreal Story | 10 Feb 2009 09:23 | 1 |
|
Time Limit on test 17 (Pascal) | Assassin | 1491. Unreal Story | 8 Dec 2008 09:19 | 8 |
Help please! I don't understand how I can make my program faster. This algorithm is slow ( n*(b-a) times). {Time Limit on test 17} var a,b,c,j:word; q:array[1..100000] of longint; i,n:longint; begin readln(n); for i:=1 to n+1 do begin readln(a,b,c); for j:=a to b do q[j]:=q[j]+c; end; write(q[1]); for i:=2 to n do write(' ',q[i]); end. Edited by author 14.09.2007 18:07 You should use such structure, as RSQ... You should use such structure, as RSQ... What is it - RSQ? no nevermind RSQ doesn't necessary Try to imagine that all what you know - it's how to sum numbers. Edited by author 07.12.2008 23:11 Simple O(N) problem RSO is humiliation. What humiliation do you mean? Humiliation of whom? It doesn't matter, simply so seems to me. |
TLE | Daniel | 1491. Unreal Story | 9 Feb 2007 11:40 | 11 |
TLE Daniel 14 Oct 2006 15:37 TLE №18 Can you please give me any hint? Re: TLE Victor Barinov (TNU) 14 Oct 2006 16:52 Try to find algo O(n^(3/2)) or O(n log n ) Re: TLE Ostap Korkuna (LNU) 15 Oct 2006 01:40 The best solution is O(n). Try to find it. Re: TLE Victor Barinov (TNU) 15 Oct 2006 02:42 O(n) ???? Are your sure??? Strange that fastest solution works in 0.125 seconds... Re: TLE Yosif Yosifov 15 Oct 2006 18:24 O(N) is without using any kind of tree , right ? Can I get a hint to this solution? ( I have already solved the problem .. ) Please, advice me how to solve this problem? Using binary tree? Thank you. I have found this O(N) solution! Just 1 minute thinking. It is really very easy. Thank you very much. If I didnt know that there is such solution I would hardly find it :) From left and from right(Because b>=a). That's the two loops?! poor English... Re: TLE KIRILL(ArcSTU) 16 Oct 2006 22:23 Edited by author 17.10.2006 02:22 |