11402 - Ahoy, Pirates!

[AmirAz]

I wrote the program based on what is on the link. 'S' is ready to answer 'I' is reverse 'E' is clear 'F' is set. the program now doesn't give the proper answer, can you tell me where am I wrong.

Code: Select all

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <set>
#include <algorithm>
#include <ctype.h>
#include <map>
#include <vector>
#include <stack>
#include <climits>
#include <functional>
#include <sstream>
#include <math.h>

using namespace std;
#define lli long long int
#define llu long long unsigned
#define ii pair<int, int>
#define vii vector<ii>
#define vi vector<int>
#define log2(n) log10(n) / log10(2)
#define getMid(a, b) floor(a + b) /2;
#define mii map<int,int>

class SegmentTree{

public:
	int tree_len, *tree; int *source; char *stat; int size;
	int build(int p, int s, int e){
		stat[p] = 'S';
		if (s == e)
			return tree[p] = (source[s]);
		int mid = getMid(s, e);
		return tree[p]  = build((p<<1), s, mid) + build((p<<1) + 1, mid + 1, e);
	}
	SegmentTree(int *ex , int n){
		size  = n;
		int h = ceil(log2(size));
		source = new int [n]; stat = new char [n];
		for (int i = 0; i < n; i++)
			source[i] = ex[i];
		tree_len = 2 * pow(2, h);
		tree = new int[tree_len+1];
		build(1, 0, size-1);
	}

	void rUpdate(int p, int s, int e, int qs, int qe, char com){
		if (s > qe || e < qs)
			return;
		
		if (s == e){
			if (com == 'I') tree[p] =(tree[p] == 1? 0 : 1);
			else if (com == 'F') tree[p] = 1;
			else source[s] = tree[p] = 0;
			stat[p] = 'S';
		}
		else{
			int mid = getMid(s, e);
			if (e <= qe && s >= qs){
				stat[p] = com; int range = e -s + 1;
				if (stat[p] == 'F') tree[p] = range;
				else if (stat[p] == 'E') tree[p] = 0;
				else if (stat[p] == 'I') tree[p] = range - tree[p];
				stat[p<<1] = stat[(p<<1) + 1] = stat[p];
				return;
			}
			rUpdate ((p<<1), s, mid, qs, qe, com);
			rUpdate ((p<<1)+ 1, mid+1, e, qs, qe, com);
			tree[p] = tree[(p<<1)] + tree[(p<<1)+1];
		}
		
		

		
	}


	int getSum(int p, int s, int e, int i, int j){
		if (s > j || e < i)
			return 0;
		if (s == e)
			return tree[p];	
		
		if ( s >= i && e <= j)
		{
			if (stat[p] == 'S')
				return tree[p];
			int range = e - s + 1;
			if (stat[p] == 'F') tree[p] = range;
			else if (stat[p] == 'E') tree[p] = 0;
			else if (stat[p] == 'I') tree[p] = range - tree[p];
			
			stat[(p<<1)+1] = stat[p<<1] = stat[p];
			stat[p] = 'S';
			return tree[p];
		}
		int mid = getMid(s, e);
		return getSum((p<<1), s, mid, i, j) + getSum((p<<1)+1, mid + 1, e, i, j);
	}
	

	
};

int main(){
	int *source = new int[1024001];
	int T; cin >> T;
	
	for (int tc = 1; tc <= T; tc++){
		int m; cin >> m;
		int size = 0;
		for (int i = 0; i < m; i++)
		{
			int time; cin >> time;
			string orig; cin >> orig;
			for (int j = 0; j < time; j++)
				for (int k = 0; k < orig.size(); k++)
					source[size++] = orig[k] - '0';
			

		}
 		SegmentTree st(source, size);
		cout << "Case " << tc << ":\n";
		int q; cin >> q; int god = 0;
		for (int i = 0; i < q; i++){
			int s, e; char a;
			cin >> a >> s >> e;
			if (a != 'S') st.rUpdate(1, 0, st.size -1, s, e, a);
			else cout << "Q"<<++god << ": " <<st.getSum(1, 0, st.size -1, s, e) << "\n";
			
			
		}

		
	}
	delete [] source;
}

[lbv]

I wrote the program based on what is on the link. (..) the program now doesn't give the proper answer, can you tell me where am I wrong.

For now, I can see a couple of things that seem a little wonky:

Inside the segment tree, I think the stat member should be of size tree_len and not n. Being shorter than needed could result in an array overflow, which is probably the cause of the most notable errors.

While on the subject of memory, every piece of memory you reserve with new should be freed with delete. You never free all that memory you reserve every time a segment tree is created. As a personal recommendation, I'd suggest to never do dynamic memory allocation inside programs for competitive programming. It usually adds a lot of complexity and subtle errors that are hard to catch for little (if any) gain. Maybe consider using C++ containers like vectors.

Also, try to avoid using floating point calculations unnecesarily. For example the getMid doesn't really need to use floor because you're dealing with integers.

There may be other issues, but you can start with these.

[AmirAz]

Hi lbv you are undoubtedly more than experienced. I got AC, tnx! Here is my working segment tree:

Code: Select all

class SegmentTree{

public:

	int tree_len, *tree; bool *source; short *situ; int size; 
	int build(int p, int s, int e){
		situ[p] = S;
		if (s == e)
			return tree[p] = (source[s]?1:0);
		int mid = getMid(s, e);
		return tree[p]  = build((p<<1), s, mid) + build((p<<1) + 1, mid + 1, e);
	}
	SegmentTree(bool *ex , int n){
		size  = n;
		int h = ceil(log2(size)) + 1;
		
		source = ex;
		tree_len = 2 * pow(2, h);
		tree = new int[tree_len+1];
		situ = new short [tree_len+1];
		build(1, 0, size-1);
	}
	~SegmentTree(){
		delete [] tree;
		delete [] situ;		
	}
	void update(int p, int s, int e){
		if (situ[p] == S) return;
		if (situ[p] == F)
			tree[p] = e -s + 1;
		else if (situ[p] == E)
			tree[p] = 0;
		else if (situ[p] == I)
			tree[p] = (e - s + 1) - tree[p];
		
		if (s != e){
			if (situ[p] == F || situ[p] == E)
				situ[_left(p)] = situ[_right(p)] = situ[p];
			else
				situ[_left(p)] = flip(situ[_left(p)]), situ[_right(p)] = flip(situ[_right(p)]);
				
		}
		situ[p] = S;
	}

	short flip(short v){
		if (v == I) return S;
		if (v == F) return E;
		if (v == E) return F;
		return I;
	}

	void rUpdate(int p, int s, int e, int qs, int qe, short com){
		update (p, s, e);
		if (s > qe || e < qs) return;
		if (s == e){
			switch(com){
			case I : tree[p] = 1 - tree[p]; break;
			case F : tree[p] = 1; break;
			case E : tree[p] = 0; break;
			}
			
			return;
		}

		int mid = getMid(s, e);
		if (s >= qs && e <= qe){
			switch(com){
			case F :{
				tree[p] = e- s + 1;
				situ [_left(p)] = situ[_right(p)] = com;
				break;
			}
			case I :{ 
				tree[p] = (e -s + 1) - tree[p];
				situ[_left(p)] = flip(situ[_left(p)]);
				situ[_right(p)] = flip(situ[_right(p)]);
				break;
			}
			case E :{
				tree[p] = 0;
				situ [_left(p)] = situ[_right(p)] = com;
				break;
			}
			}
			
			return;
			
		}

		rUpdate (_left(p), s, mid, qs, qe, com);
		rUpdate (_right(p), mid + 1, e, qs, qe, com);
		tree[p] = tree[_left(p)] + tree[_right(p)];
	}


	int getSum(int p, int s, int e, int i, int j){
		if (e < i || s > j) return 0;
		update (p, s, e);
		if (s >= i && e <= j) return tree[p];
		int mid = getMid(s, e);
		return getSum(_left(p), s, mid, i, j) + getSum(_right(p), mid + 1, e, i, j);
	}
	

	
};

[prav90]

Hi All,

I tried solving this problem using lazy updates in Segment tree. I get TLE in Java. Can somebody provide any hints on getting AC using Java. Does it need a fast IO or is my implementation wrong? I have been working on this for a while and am stuck at this point.

My Code :

Code: Select all

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;

// each node in the Segment Tree
// stores the number of nodes in its subtree
// number of ones in its subtree
// magician cast type for lazy updates
class Node {
	int length, ones;
	char qtype;
}

class SegmentTreePirates {
	Node [] st;
	int n;
	SegmentTreePirates(StringBuilder arr, int n) {
		this.n = n;
		st = new Node[4*n]; 
		// we ignore index 0 in the segment tree
		for(int i = 1; i < 4*n; i++)
			st[i] = new Node();
		build(1, 0, n-1, arr);
	}
	
	/* return right and left childs of the given index */
	private int left(int i) { return i<<1; }
	private int right(int i) { return (i<<1)+1; }
	
	// construct the segment tree from the given array recursively
	private void build(int index, int l, int r, StringBuilder arr) {
		// check if we have reached a leaf node
		if(l == r) {
			st[index].length = 1;
			st[index].qtype = 9999; // flag value indicating no updates
			if(arr.charAt(l) == '1') st[index].ones = 1;
			else st[index].ones = 0;
		}
		else { // build the tree recursively
			int mid = (l+r)/2;
			build(left(index), l, mid, arr);
			build(right(index), mid + 1, r, arr);
			st[index].qtype = 9999;
			st[index].ones = st[left(index)].ones + st[right(index)].ones;
			st[index].length = (r-l+1);
		}
	}
	
	public void update(int l, int r, char type) {
		update(1, 0, n-1, l, r, type);
	}
	
	private void changeType(int i, char type) {
		if(type == 'I') {
			switch(st[i].qtype)
			{
				case 'F' :
					st[i].qtype = 'E';
					break;
				case 'E' :
					st[i].qtype = 'F';
					break;
				case 'I' :
					st[i].qtype = 9999;
					break;
				case 9999 :
					st[i].qtype = 'I';
					break;
				
			}
		}
		else {
			st[i].qtype = type;
		}
	}
	// performs the update operation based on the qtype
	private void update( int index ) {
		switch(st[index].qtype) {
			case 'F' :
				st[index].ones = st[index].length;
				break;
			case 'E' :
				st[index].ones = 0;
				break;
			case 'I' :
				st[index].ones = st[index].length - st[index].ones;
		}
	}
	
	private void update(int index, int l, int r, int i, int j, char type) {
		// if tree range is within the update range
		if(l >= i && r <= j) 
			changeType(index, type);
		if(st[index].qtype != 9999) {
			update(index);
			// marks its children as lazy if it's not the leaf node
			if(l != r) {
				//System.out.println("Index : " + index +" l : " + l + " r : " +r);
				changeType(left(index), st[index].qtype);
				changeType(right(index), st[index].qtype);
			}
			// unset the lazy update qtype
			st[index].qtype = 9999;
		}
		// within the range
		if(l >= i && r <= j) return;
		// return if outside the range
		else if(l > j || r < i) return;
		else {
			int mid = (l+r)/2;
			update(left(index), l, mid, i, j, type);
			update(right(index), mid+1, r, i, j, type);
			st[index].ones = st[left(index)].ones + st[right(index)].ones;
		}
	}
	
	public int query(int i, int j) {
		return query(1, 0, n-1, i, j);
	}
	
	private int query(int index, int l, int r, int i, int j) {
		//System.out.println("Index : " + index +" l : " + l + " r : " +r);
		if(st[index].qtype != 9999) {
			update(index);
			// marks its children as lazy if it's not the leaf node
			if(l != r) {
				//System.out.println("Index : " + index +" l : " + l + " r : " +r);
				changeType(left(index), st[index].qtype);
				changeType(right(index), st[index].qtype);
			}
			// unset the lazy update qtype
			st[index].qtype = 9999;
		}
		if(l >= i && r <= j) return st[index].ones;
		if(l > j || r < i) return 0;
		int mid = (l+r)/2;
		
		int ans = query(left(index), l, mid, i, j) + query(right(index), mid+1, r, i, j);
		st[index].ones = st[left(index)].ones + st[right(index)].ones;
		return ans;
	}
}

public class Main {
	public static void main(String [] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T;t++) {
			pw.println("Case "+t+":");
			int reps = Integer.parseInt(br.readLine());

			StringBuilder ip = new StringBuilder("");
			for(int i = 0; i < reps; i++) {
				int repCnt = Integer.parseInt(br.readLine());
				String repStr = br.readLine();
				while(repCnt-- > 0)
					ip.append(repStr);
			}
			
			
			SegmentTreePirates st = new SegmentTreePirates(ip, ip.length());
			int q = Integer.parseInt(br.readLine());
			int godsQ = 0;
			while(q-- > 0) {
				StringTokenizer sz = new StringTokenizer(br.readLine());
				char type = sz.nextToken().charAt(0);
				int a = Integer.parseInt(sz.nextToken());
				int b = Integer.parseInt(sz.nextToken());
				
				if(type == 'S') {
					godsQ++;
					pw.println("Q"+godsQ+": "+st.query(a, b));
				}
				else {
					st.update(a, b, type);
				}
			}
		}
		pw.close();
	}
}

Thanks

[Repon kumar Roy]

Getting TLE and
There is some mismatch between brianfry i/o ... But could not find the error

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>
#include <sstream>
using namespace std;


#define MX 1024005
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define pb push_back
#define pop pop_back


ll x,y,d;


#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))
#define gc getchar_unlocked
template<class T > void sc(T &x){
        register T c = gc();
        x = 0;
        for(;(c<48 || c>57);c = gc());
        for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
}

template < class T > inline T gcd(T a , T b ) { if(b==0) return a; else return gcd(b, a%b);}
template < class T > inline T lcm(T a , T b ) { return  a*b / gcd(a, b);}
template < class T > inline T extended_euclid_returning_gcd(T a,T b){ T t; if(b==0){d = a;x=1;y=0;} else {extended_euclid_returning_gcd(b, a%b); t=x; x=y;y = t-(a*y/b);}}
template < class T > inline T absolute(T a ) { if(a>0) return a; else return -a;}
template < class T > inline T reverse_num( T a ){ T x=0,tmp = a; while(tmp) { x=10*x+ tmp % 10; tmp/=10;} return x;}
template <class T > inline T big_mod(T base, T power){ T res=1; while (power) { if(power&1){ res*=base; power--;} base =base *base; power/=2;} return res;}


string tmp , manl ;

int T[4*MX];
int lazy[4*MX];


void bulid( int n, int b,int e)
{
        if(b==e){
                T[n] = (manl[b] == '1' ? 1 : 0);
                lazy[n] = 0;
                return;
        }
        
        int mid = (b + e)/2;
        bulid(2*n , b, mid );
        bulid(2*n+1, mid +1, e);
        
        T[n] = T[2*n] + T[2*n+1];
       lazy[n] = 0;
        return;
        
}

#define UP_SET 99
#define UP_CLR 9999
#define UP_FLIP 99999

void flip (int& n)
{
        if(n == UP_CLR)n = UP_SET;
        if(n == UP_SET) n = UP_CLR;
        if(n == UP_FLIP) n = 0;
        if(n== 0) n = UP_FLIP;
        
        return ;
}
void upd (int n,int b,int e ,int i,int j,int val)
{
        if(lazy[n]!=0){
                if(lazy[n] == UP_SET){
                        T[n] = (e-b+1);
                        if(b!=e){
                                lazy[2* n] = UP_SET;
                                lazy[2* n + 1] = UP_SET;
                        }
                }
                if(lazy[n] == UP_CLR ){
                        T[n] = 0;
                        if(b!=e){
                                lazy[2* n] = UP_CLR;
                                lazy[2* n + 1] = UP_CLR;
                        }
                }
                if(lazy[n] == UP_FLIP) {
                        T[n] = e-b+1 - T[n];
                        if(b!=e){
                                flip(lazy[2*n]);
                                flip(lazy[2*n+1]);
                        }
                }
                lazy[n] = 0;
                
        }
        
        if(b >j || e < i || i > j ) return;
        if( b == i && e == j ){
                
                if(val == UP_SET){
                        T[n] = (e-b+1);
                        if(b!=e){
                                lazy[2* n] = UP_SET;
                                lazy[2* n + 1] = UP_SET;
                        }
                }
                if(val== UP_CLR ){
                        T[n] = 0;
                        if(b!=e){
                                lazy[2* n] = UP_CLR;
                                lazy[2* n + 1] = UP_CLR;

                        }
                }
                if(val== UP_FLIP) {
                        T[n] = e-b+1 - T[n];
                        if(b!=e){
                                flip(lazy[2*n]);
                                flip(lazy[2*n+1]);
                        }
                }
                return ;
                
        }
        
        int mid = (b + e)/2;
        upd(2*n, b, mid, i, min(j,mid), val);
        upd(2*n+1, mid+1, e, max(i,mid + 1), j, val);
        
        T[n] = T[2*n] + T[2*n+1];
        return;
        
}

int que ( int n,int b,int e,int i,int j)
{
        if(lazy[n]!=0){
                if(lazy[n] == UP_SET){
                        T[n] = (e-b+1);
                        if(b!=e){
                                lazy[2* n] = UP_SET;
                                lazy[2* n + 1] = UP_SET;
                        }
                }
                if(lazy[n] == UP_CLR ){
                        T[n] = 0;
                        if(b!=e){
                                lazy[2* n] = UP_CLR;
                                lazy[2* n + 1] = UP_CLR;
                        }
                }
                if(lazy[n] == UP_FLIP) {
                        T[n] = e-b+1 - T[n];
                        if(b!=e){
                                flip(lazy[2*n]);
                                flip(lazy[2*n+1]);
                        }
                }
                lazy[n] = 0;
                
        }
        if(b >j || e < i || i > j ) return 0 ;
        if( b == i && e == j ){
                return T[n];
        }
        
        int mid = ( b  + e )/2;
        int p1 = que(n *2, b, mid , i, min(j,mid));
        int p2 = que(2*n+1, mid+1, e, max(i,mid+1), j);
        
        return p1+p2;
}

int main()

{
        
        
        int test,q,cs=0,times,i,j, m ;
        char ch;
        //for(int i =0 ;  i < 3 *MX; i++) lazy[i] = 0;
        //freopen("in.txt", "r", stdin);
        sc(test);
        
        while (test--) {
                
                printf("Case %d:\n",++cs);
                sc(m);
                for (; m--; ) {
                        sc(times);
                        string a;
                        cin>>tmp;
                        if(tmp.compare("") == 0){
                                cin >> tmp;
                        }
                        while (times--) {
                                a = a + tmp;
                        }
                        manl = manl + a;
                }
                int sz = (int) manl.length();
                cout << manl << endl;
                bulid(1, 0, sz-1);
                
                sc(q);
                int qno = 0;
                while (q--) {
                        do {
                                ch = getchar();
                        } while (ch=='\n'|| ch=='\0' || ch==' ' );
                        
                        sc(i); sc(j);
                        if(ch=='F')   upd(1, 0, sz -1 , i, j, UP_SET);
                        else if(ch=='E')  upd(1, 0, sz-1, i, j, UP_CLR);
                        else if(ch=='I')   upd(1, 0, sz-1, i, j, UP_FLIP);
                        
                        else if(ch=='S') {
                                int res = que(1, 0, sz-1, i, j);
                                printf("Q%d: %d\n",++qno , res);
                        }
                        
                }
                ms(lazy, 0);
                ms(T, 0);
                manl.clear();
        }
        
        
        return 0;
        
}

/*
 2
 2
 5
 10
 2
 1000
 5
 E 0 17
 S 0 8
 F 0 8
 S 0 8
 S 0 17
 */

[Lim.YuDe]

Using segment tree with lazy propagation, but still getting TLE.
Any help would be greatly appreciated!

EDIT: edited the code to implement lazy propagation properly, and I have no TLE now but I get RTE instead.. which is weird because I don't get that error when I test my super large input. I must be missing something..

Code: Select all

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

#define REP(a, b, c) \
    for (int a = int(b); a < c; a++)

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<char> vc;

class SegmentTree {
private:
    vi st;
    vc A, lazy;
    int n;
    int left (int p) { return p << 1; }
    int right (int p) { return (p << 1) + 1; }

    void performLazy(int p, int L, int R) {
        if (lazy[p] == '\0') return;
        if (lazy[p] == 'F') {
            st[p] = (R-L+1);
        } else if (lazy[p] == 'E') {
            st[p] = 0;
        } else if (lazy[p] == 'I') {
            st[p] = (R-L+1) - st[p];
        }
        //printf("Performed laziness:%c to L,R:%d,%d; st[%d] = %d\n", lazy[p], L, R, p, st[p]);
        if (L != R) {
            int l = left(p);
            int r = right(p);
            //performLazy(left(p), L, (L+R)/2);
            //performLazy(right(p), (L+R)/2+1, R);
            if (lazy[p] == 'F' || lazy[p] == 'E') {
                lazy[l] = lazy[r] = lazy[p];
            } else if (lazy[p] == 'I') {
                if (lazy[l] == 'I') {
                    lazy[l] = '\0';
                } else if (lazy[l] == 'F') {
                    lazy[l] = 'E';
                } else if (lazy[l] == 'E') {
                    lazy[l] = 'F';
                } else {
                    lazy[l] = lazy[p];
                }
                if (lazy[r] == 'I') {
                    lazy[r] = '\0';
                } else if (lazy[r] == 'F') {
                    lazy[r] = 'E';
                } else if (lazy[r] == 'E') {
                    lazy[r] = 'F';
                } else {
                    lazy[r] = lazy[p];
                }
            }
        }
        lazy[p] = '\0';
    }
    void build (int p, int L, int R) {
        if (L > R) return;
        if (L == R) { // leaf
            st[p] = (A[L] == '1');
            //printf("L,R:%d,%d; st[%d] = %d\n", L, R, p, st[p]);
            return;
        }
        build(left(p),  L,          (L+R)/2 );
        build(right(p), (L+R)/2+1,  R       );
        st[p] = st[left(p)] + st[right(p)];
        if (p == 3) {
            //printf("st[%d] = st[%d] + st[%d]\n", p, left(p), right(p));
            //printf("L,R:%d,%d; st[%d] = %d\n", L, R, p, st[p]);
        }
    }
    int query(int p, int L, int R, int i, int j) {
        if (L > R || L > j || R < i) return 0;
        performLazy(p, L, R);
        if (L >= i && R <= j) {
            //printf("Query:L,R:%d,%d, i,j:%d,%d st[%d] = %d\n", L, R, i, j, p, st[p]);
            return st[p];
        }
        int q1 = query(left(p),     L,          (L+R)/2,    i, j);
        int q2 = query(right(p),    (L+R)/2+1,  R,          i, j);
        //printf("Query:L,R:%d,%d, i,j:%d,%d q1+q2 = %d\n", L, R, i, j, q1+q2);
        return q1 + q2;
    }
    void update(int p, int L, int R, int i, int j, char command) {
        performLazy(p, L, R);
        if (L > R || L > j || R < i) return;
        if (L >= i && R <= j) {
            lazy[p] = command;
            performLazy(p, L, R);
            //printf("Performed command:%c to L,R:%d,%d; st[%d] = %d\n", command, L, R, p, st[p]);
            return;
        }
        update(left(p),     L,          (L+R)/2,    i, j, command);
        update(right(p),    (L+R)/2+1,  R,          i, j, command);
        st[p] = st[left(p)] + st[right(p)];
        //printf("st[%d] = st[%d] + st[%d]\n", p, left(p), right(p));
        //printf("L,R:%d,%d; st[%d] = %d\n", L, R, p, st[p]);
    }
public:
    SegmentTree(const vc& _A) {
        A = _A;
        n = (int)A.size();
        st.assign(3*n, 0);
        lazy.assign(3*n, '\0');
        build(1, 0, n-1);
    }
    int query(int i, int j) {
        return query(1, 0, n-1, i, j);
    }
    void update(char command, int a, int b) {
        update(1, 0, n-1, a, b, command);
    }
};

char line[51] = "000000111111111111";
vc pirates;
int t, m, repeats, q, qNo, a, b;

int main() {
    scanf("%d", &t);
    REP(caseNo, 1, t+1) {
        printf("Case %d:\n", caseNo);

        pirates.clear();
        scanf("%d", &m);
        while (m--) {
            scanf("%d %s", &repeats, line);
            while (repeats--) {
                REP(i, 0, strlen(line)) pirates.push_back(line[i]);
            }
        }

        SegmentTree st(pirates);
        //printf("Initial number of buccaneer pirates: %d\n", st.query(0, pirates.size()-1));
        scanf("%d", &q);
        qNo = 1;
        while (q--) {
            scanf("%s %d %d", line, &a, &b);
            if (line[0] == 'S') {
                printf("Q%d: %d\n", qNo++, st.query(a, b));
            } else {
                st.update(line[0], a, b);
                //printf("Updated buccaneer pirates: %d\n", st.query(0, pirates.size()-1));
            }
            //printf("TEST: query(%d,%d) = %d\n", 999999, 999999, st.query(999999,999999));
            //printf("TEST: query(%d,%d) = %d\n", 500000, 999999, st.query(500000,999999));
        }
    }

    return 0;
}

[just_yousef]

hey,
Im getting TLE using segment tree with lazy propagation.
this is my code: http://ideone.com/3QmSt8
any help please.

[asrajmane193]

I am getting Runtime error for this code. Could someone please help me with that?

http://ideone.com/btRZKZ

[asrajmane193]

I updated my code a little. Here's the updated IDEone. http://ideone.com/r09PKO

[asrajmane193]

Runtime error gone, but now TLE.

I was able to find out the offending statements causing the segmentation fault. Inside "propagate()" function the lines 57, 58, 62, 63, 67, 68 were the culprits - I had not put a condition to end the propagation at the leaf nodes.

Code that's giving TLE is here - http://ideone.com/JjPtwu

It'd be great help if someone could look into it.

[bluemmb22]

Runtime error gone, but now TLE.

I was able to find out the offending statements causing the segmentation fault. Inside "propagate()" function the lines 57, 58, 62, 63, 67, 68 were the culprits - I had not put a condition to end the propagation at the leaf nodes.

Code that's giving TLE is here - http://ideone.com/JjPtwu

It'd be great help if someone could look into it.

I Just change your string concatenation and your code got ACCEPTED . strcat have an overhead for creating new array of char and copy both arguments to new one , so you can just do like this :

Code: Select all

for (int j = 0; j < r; j++)
	for (int k =0 ; k< l ;k++)
		desc[n++] = seq[k];

[leolleo]

My code passes on all the random test cases generated by the program i've written and the random test case provided by UDebug. Unfortunatelly i'm still getting WA at ~4.334 sec. Can anyone help me?

The code is this: https://ideone.com/KuwNo1

[asrajmane193]

Thanks leolleo, that worked.

[mamun4122]

I am getting wrong answer.I alredy tried test case from udebug.All of my output is correct.can someone give me any test case?

Code: Select all

//got AC

[lusho]

hello everyone
I am getting TLE but i do not know why?? please could you tell me, what I am doing bad?? I use Segment tree + Lazy Propagation it is my first implementation, thank you everyone, here is my code:

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define MAX 1024600
struct Seg
{
	int bucan;
	int barba;
	char lazy;
};
vector<Seg> ST(MAX*4);
string s,aux;
Seg sum(Seg a,Seg b)
{
	Seg n;
	n.bucan=a.bucan+b.bucan;
	n.barba=a.barba+b.barba;
	n.lazy='a';
	return n;
}
void Segment_Tree(int nodo,int i,int j)
{
	if(i==j)
	{
		ST[nodo].barba=0;
		ST[nodo].bucan=0;
		if(s[i]=='1')
			ST[nodo].bucan=1;
		else
			ST[nodo].barba=1;
		ST[nodo].lazy='a';
		return;
	}
	int mid=(i+j)>>1;
	int izq=nodo<<1;
	int der=izq+1;
	Segment_Tree(izq,i,mid);
	Segment_Tree(der,mid+1,j);
	ST[nodo]=sum(ST[izq],ST[der]);
}
void lazy_propagation(int nodo,int a,int b,char opc)
{
	if(ST[nodo].lazy=='a' )
	{
		ST[nodo].lazy=opc;
	}
	else
	{
		if(ST[nodo].lazy=='F')
		{
			ST[nodo].bucan=b-a+1;
			ST[nodo].barba=0;
		}
		else
		{
			if(ST[nodo].lazy=='E')
			{
				ST[nodo].barba=b-a+1;
				ST[nodo].bucan=0;
			}
			else
			{
				if(ST[nodo].lazy=='I')
				{
					swap(ST[nodo].barba,ST[nodo].bucan);
				}
			}
		}
		int mid=(a+b)>>1;
		int izq=nodo<<1;
		int der=izq+1;
		if(a==b)
		{
			ST[nodo].lazy=opc;
			return;
		}
		lazy_propagation(izq,a,mid,ST[nodo].lazy);
		lazy_propagation(der,mid+1,b,ST[nodo].lazy);
		ST[nodo].lazy=opc;
	}
}
void update(int nodo,int i,int j,int a,int b,char opc)
{
	if(ST[nodo].lazy!='a')
	{
		lazy_propagation(nodo,i,j,ST[nodo].lazy);
		ST[nodo].lazy='a';
	}
	if(i>b || j<a) return;
	if(i>=a && j<=b)
	{
		if(opc=='F')
		{
			ST[nodo].bucan+=ST[nodo].barba;
			ST[nodo].barba=0;
		}
		else
		{
			if(opc=='E')
			{
				ST[nodo].barba+=ST[nodo].bucan;
				ST[nodo].bucan=0;
			}
			else
			{
				if(opc=='I')
				{
					swap(ST[nodo].barba,ST[nodo].bucan);
				}
			}
		}
		int mid=(i+j)>>1;
		int izq=nodo<<1;
		int der=izq+1;
		if(i==j)
		{
			return;
		}
			lazy_propagation(izq,i,mid,opc);
			lazy_propagation(der,mid+1,j,opc);
			return;
	}
	int mid=(i+j)>>1;
	int izq=nodo<<1;
	int der=izq+1;
	update(izq,i,mid,a,b,opc);
	update(der,mid+1,j,a,b,opc);
	ST[nodo].bucan=ST[izq].bucan+ST[der].bucan;
	ST[nodo].barba=ST[izq].barba+ST[der].barba;
}
Seg query(int nodo,int i,int j,int a,int b)
{
	if(ST[nodo].lazy!='a')
	{
		lazy_propagation(nodo,i,j,ST[nodo].lazy);
		ST[nodo].lazy='a';
	}
	if(i>=a && j<=b)
		return ST[nodo];
	int mid=(i+j)>>1;
	int izq=nodo<<1;
	int der=izq+1;
	if(mid>=b)
	{
		return query(izq,i,mid,a,b);
	}
	else
	{
		if(mid+1<=a)
		{
			return query(der,mid+1,j,a,b);
		}
		else
		{
			return sum(query(izq,i,mid,a,b),query(der,mid+1,j,a,b));
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tc,n,veces,que,a,b;
	char opc;
	cin>>tc;
	for(int cp=1;cp<=tc;cp++)
	{
		s="";
		cout<<"Case "<<cp<<":"<<'\n';
		cin>>n;
		while(n--)
		{
			cin>>veces;
			cin>>aux;
			while(veces--)
			{
				s=s+aux;
			}
		}
		int tam=s.size()-1;
		Segment_Tree(1,0,tam);
		cin>>que;
		int qq=0;
		while(que--)
		{
			cin>>opc>>a>>b;
			if(opc=='S')
			{
				cout<<"Q"<<++qq<<": "<<query(1,0,tam,a,b).bucan<<'\n';
			}
			else
			{
				update(1,0,tam,a,b,opc);
			}
		}
	}
	return 0;
}