Page 1 of 1

Re: 1136 - Help R2-D2!

Posted: Sun Jul 05, 2015 6:56 pm
by Repon kumar Roy
Using Segment Tree , I am getting TLE ??
Isn't input terminates with EOF ??
My code :

Code: Select all


#include <bits/stdc++.h>
using namespace std;

/*------- Constants---- */
#define LMT                     1000006
#define ll                      long long
#define ull                     unsigned long long
#define mod                     1000000007
#define MEMSET_INF              63
#define MEM_VAL                 1061109567
#define FOR(i,n)                for( int i=0 ; i < n ; i++ )
#define mp(i,j)                 make_pair(i,j)
#define lop(i,a,b)              for( int i = (a) ; i < (b) ; i++)
#define pb(a)                   push_back((a))
#define gc                      getchar_unlocked
#define PI                      acos(-1.0)
#define inf                     1<<30
#define lc                      ((n)<<1)
#define rc                      ((n)<<1 |1)
#define debug(x)                cout <<#x <<" -> " << x << endl;
#define EPS                     1e-9

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
typedef pair<int, int> ii;
typedef vector<int > vi ;
/*------ template functions ------ */
inline void sc(int &x)
{
	register int c = gc();
	x = 0;
	int neg = 0;
	for(;((c<48 | c>57) && c != '-');c = gc());
	if(c=='-') {neg=1;c=gc();}
	for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
	if(neg) x=-x;
}

template <class T> inline T bigmod(T p,T e,T M){
	ll ret = 1;
	for(; e > 0; e >>= 1){
		if(e & 1) ret = (ret * p) % M;
		p = (p * p) % M;
	} return (T)ret;
}
template <class T> inline T gcd(T a,T b){if(b==0)return a;return gcd(b,a%b);}
template <class T> inline T modinverse(T a,T M){return bigmod(a,M-2,M);}

/*************************** END OF TEMPLATE ****************************/

int iAr[LMT];
int block;
int DP[3 * LMT];
char s[100];

void upd( int n , int b , int e ,int val ){
      if( b == e ) {
            iAr[b] -= val;
            DP[n] -= val;
            return;
      }
      int mid = (b+e)/2;
      if(DP[lc] >= val ) {
            upd(lc, b, mid, val);
      }
      else upd(rc, mid+1, e, val);
      DP[n] = max(DP[lc] , DP[rc]);
}
int main()
{
      int cap , boxes , tc = 0 ;
	while(scanf("%d" ,& cap) == 1) {
            
            scanf("%d" , &boxes );
            for(int i = 0; i < boxes ; i ++ ) iAr[i] = cap;
            block = sqrt(LMT ) + 1;
            
            for(int i = 0; i < 3 * boxes + 5 ; i ++ ) DP[i] = cap;
            
            for( int i = 0 ; i < boxes ; i ++ ) {
                  scanf("%s" , s);
                  if(s[0] == 'b' ) {
                        int lo , u ;
                        scanf("%d %d",&lo,&u );
                       
                        for( int j = 0 ; i < boxes && j < lo ; i ++ , j ++ ) {
                              upd(1, 0, boxes - 1, u);
                        }
                        i --;
                  }
                  else {
                        int sum = 0;
                        for(int i = 0; s[i] ; i ++ ) {
                              sum = 10  * sum + s[i] -'0';
                        }
                        upd(1, 0, boxes - 1, sum);
                        
                  }
            }
            ll ans = 0 ,cnt = 0 ;
            for( int i = 0; i < boxes ; i ++ ) {
                  if(iAr[i] == cap ) break;
                  else {
                        cnt++ ;
                        ans += iAr[i];
                  }
            }
            if( tc) printf("\n");
            printf("%lld %lld\n" , cnt , ans);
            tc = 1;
      }
	
	return 0;
}