c++ - Segment Tree with lazy propagation Time limit problem -


the following implementation of http://www.spoj.pl/problems/lite/ using segment tree's lazy propagation. new segment trees , cannot understand why getting tle. please @ , me correct error?

#include <iostream> #include <iostream> #include <cstdio> #include <cstring> #define max 100000 using namespace std; int m[2*max+1]; int flag[2*max+1]; int count; void refresh(int begin,int end,int n) {     m[n] = end-begin+1 - m[n];     flag[n]=0;     flag[n*2] =!flag[n*2];     flag[n*2+1] =!flag[n*2+1]; } void update(int begin,int end,int i,int j,int n=1) {     if(flag[n])     {         refresh(begin,end,n);     }     if(begin>=i && end<=j)     {         if(!flag[n])         {             refresh(begin,end,n);         }         flag[n] = 0;         return;     }     else if(begin>=end)     {         return;     }     else     {         int mid = (begin+end)>>1;         if(i<=mid)         {             update(begin,mid,i,j,n*2);         }         if(j>mid)         {             update(mid+1,end,i,j,n*2+1);         }         if(flag[2*n])         {             refresh(begin,mid,2*n);         }         if(flag[2*n+1])         {             refresh(mid+1,end,2*n+1);         }         m[n] = m[n*2]+ m[n*2+1];     } } int query(int begin,int end,int i,int j,int n=1) {     if(flag[n])     {         refresh(begin,end,n);     }     if(begin>=i && end<=j)     {         return m[n];     }     if(begin>=end)     {         return 0;     }     int mid = (begin+end)>>1;     int l=0,r=0;     if(i<=mid)     {         l = query(begin,mid,i,j,n*2);     }     if(j>mid)     {         r = query(mid+1,end,i,j,n*2+1);     }     if(flag[2*n])     {         refresh(begin,mid,2*n);     }     if(flag[2*n+1])     {         refresh(mid+1,end,2*n+1);     }     m[n] = m[n*2]+ m[n*2+1];     return l+r; } int main() {     memset(m,0,sizeof m);     int n,m,a,b,c;     scanf("%d%d",&n,&m);     for(int i=0; i<m; i++)     {         scanf("%d%d%d",&a,&b,&c);         if(a==0)         {             update(1,n,b,c);         }         else         {             printf("%d\n",query(1,n,b,c));         }     }     return 0; }

m[node]^=1; might faster m[node] = (m[node]==0)?1:0;, , (begin+end)>>1 faster (begin/end)/2, not relevant

le: try if making recursive functions inline run faster. think unravels recursion couple of times , works little bit faster. maybe sending parameters references make run faster, try out. if test cases chosen still shouldn't able pass tests trickery, helps sometimes.


Comments

Post a Comment

Popular posts from this blog

c++ - Is it possible to compile a VST on linux? -

for class project i'm attempting write vst plugin backed cuda. current cuda workflow on linux box, i'd prefer compile , link there. according wikipedia , should possible (i couldn't find steinberg documentation relevant linux) can't find makefile or instructions on how build if aren't using xcode or visual studio. i'm vst 3 sdk doesn't support linux. when try compile plugin under linux, error: ./base/source/fatomic.cpp:39:30: fatal error: libkern/osatomic.h: no such file or directory this issue caused following code in "vst3 sdk/base/source/fatomic.cpp" #if mac #include <libkern/osatomic.h> #if mac_os_x_version_min_required > mac_os_x_version_10_4 #define native_atomic_type (volatile int32_t*) #else #define native_atomic_type (int32_t*) #endif #elif windows #include <windows.h> #endif but hope compiling under linux work vst sdk 2.4. reading. jvstwrapper seems run on lin...
Read more

java - Output of Eclipse is rubbish -

i want write program in eclipse language different english. when display output using system.out program, displays output correctly in console editor. when accept input console , output it, output rubbish. how can solve it. many thnaks i'm not sure if problem, have character encoding problem. make sure you're using unicode, utf-8. you can read more @ official docs converting non-unicode text .
Read more

jquery - Confused with JSON data and normal data in Django ajax request -

i read json internet still have not got grasp of it. reading article http://webcloud.se/log/ajax-in-django-with-jquery/ i not understood first part function using json def xhr_test(request, format): if request.is_ajax(): if format == 'xml': mimetype = 'application/xml' if format == 'json': mimetype = 'application/javascript' data = serializers.serialize(format, examplemodel.objects.all()) return httpresponse(data,mimetype) # if want prevent non xhr calls else: return httpresponse(status=400) my main problems are from function getting format variable does format json mean data given function json or data recived json can give me simple example ouput of function data = serializers.serialize(format, examplemodel.objects.all()) how use data when response in jquery function if don't use json in above function how input , response chnage thanks ...
Read more