|
|
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. #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 . случайно Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 Edited by author 08.12.2020 04:24 This problem is very easy. I use idea similar dp. Edited by author 30.05.2018 19:11 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) [code deleted] Edited by author 20.10.2006 23:12 Edited by moderator 01.12.2019 21:13 Algo is O(2n) The same algo on Pascal got AC in 0.156 sec Thank you Alexander, my algorithm AC 0.484 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. 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 №18 Can you please give me any hint? Try to find algo O(n^(3/2)) or O(n log n ) The best solution is O(n). Try to find it. O(n) ???? Are your sure??? Strange that fastest solution works in 0.125 seconds... O(N) is without using any kind of tree , right ? Can I get a hint to this solution? ( I have already solved the problem .. ) I got a AC, thx. 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... Edited by author 17.10.2006 02:22 |
|
|