Multiples of 3 | CodeChef Solution

Hello coders, today we are going to solve Multiples of 3 CodeChef Solution whose Problem Code is MULTQ3.

Multiples of 3

Contents

Task

There are N numbers a[0],a[1]..a[N – 1]. Initally all are 0. You have to perform two types of operations :

1) Increase the numbers between indices A and B by 1. This is represented by the command “0 A B”

2) Answer how many numbers between indices A and B are divisible by 3. This is represented by the command “1 A B”.

Input Format

The first line contains two integers, N and Q. Each of the next Q lines are either of the form “0 A B” or “1 A B” as mentioned above.

Output Format

Output 1 line for each of the queries of the form “1 A B” containing the required answer for the corresponding query.

Sample Input

4 7
1 0 3
0 1 2
0 1 3
1 0 0
0 0 3
1 3 3
1 0 3

Sample Output

4
1
0
2

Constraints

  • 1 <= N <= 100000
  • 1 <= Q <= 100000
  • 0 <= A <= B <= N – 1

Solution – Multiples of 3

C++

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

#define endl "\n"
#define tab "\t"
#define int long long
#define fastio ios_base::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL)
#define F first
#define S second
#define pi pair<int, int>
#define maxpq priority_queue<int>
#define minpq priority_queue<int, vector<int>, greater<int>>
#define inf (int) (1e18)
#define vi vector<int>
#define vpi vector<pi>
#define sz(v) (int)v.size()
#define for0(i, n) for(int i = 0; i < n; i++)
#define pb emplace_back
#define prec(n) fixed<<setprecision(n)
#define debug(x) cout << #x << ": " << x << endl


const int mod = (int)(1e9 + 7);
const int MAXN =  (int)((1e5) + 100);
int max(int a, int b) { if(a > b) return a; else return b;}
int min(int a, int b) { if(a > b) return b; else return a;}
int gcd(int a, int b) { if(a == 0) return b; return gcd(b%a, a);}
const int dx[4] = { 0, -1, 0, 1};
const int dy[4] = { -1, 0, 1, 0};
const int N = (int)(4 * 1e5 + 10);
vector<int> adj[N];

void constructor()
{
	fastio;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif

}

//-----------------------------------------------------------------------------------
struct box
{
	int zero, one, two;
};


box tree[N];
int lazy[N];

void buildTree(int index, int start, int end)
{
	if(start == end)
	{
		tree[index].zero = 1;
		tree[index].one = 0;
		tree[index].two = 0;
		return;
	}

	int mid = start + ((end - start) >> 1);
	buildTree(2 * index, start, mid);
	buildTree(2 * index + 1, mid + 1, end);

	tree[index].zero = tree[2 * index].zero + tree[2 * index + 1].zero;
	tree[index].one = tree[2 * index].one + tree[2 * index + 1].one;
	tree[index].two = tree[2 * index].two + tree[2 * index + 1].two;
}

void shift(int index)
{
	int temp0 = tree[index].zero;
	int temp1 = tree[index].one;
	int temp2 = tree[index].two;

	tree[index].zero = temp2;
	tree[index].one = temp0;
	tree[index].two = temp1;
}

void handleLazy(int index, int start, int end)
{
	if(lazy[index] > 0)
	{
		int temp = lazy[index];
		lazy[index] = 0;

		if(start != end)
		{
			lazy[2 * index] += temp;
			lazy[2 * index + 1] += temp;
		}
		temp %= 3;

		for(int i = 0; i < temp; i++)
			shift(index);
	}
}


void update(int index, int start, int end, int L, int R)
{	
	handleLazy(index, start, end);

	if(end < L || R < start)
		return;
	else if(L <= start && end <= R)
	{
		shift(index);

		if(start != end)
		{
			lazy[2 * index]++;
			lazy[2 * index + 1]++;
		}
		return;
	}
	

	int mid = start + ((end - start) >> 1);
	update(2 * index, start, mid, L, R);
	update(2 * index + 1, mid + 1, end, L, R);

	tree[index].zero = tree[2 * index].zero + tree[2 * index + 1].zero;
	tree[index].one = tree[2 * index].one + tree[2 * index + 1].one;
	tree[index].two = tree[2 * index].two + tree[2 * index + 1].two;
}


int query(int index, int start, int end, int L, int R)
{
	handleLazy(index, start, end);

	if(end < L || R < start)
		return 0;
	else if(L <= start && end <= R)
		return tree[index].zero;

	int mid = start + ((end - start) >> 1);
	int left = query(2 * index, start, mid, L, R);
	int right = query(2 * index + 1, mid + 1, end, L, R);
	return left + right;
}




void runtestcase()
{
	
    int n, q, type, L, R;
    cin >> n >> q;
    buildTree(1, 0, n - 1);

    while(q--)
    {
    	cin >> type;
    	if(type == 0)
    	{
    		cin >> L >> R;
    		update(1, 0, n - 1, L, R);
    	}
    	else
    	{
    		cin >> L >> R;
    		cout << query(1, 0, n - 1, L, R) << endl;
    	}
    }
}



signed main(){
    
    constructor();
    int tc=1;
    //cin >> tc;
    while(tc--)
        runtestcase();
    return 0;
}

Java

import java.io.*;

class Spoj
{
    static int n,q;
    static Node st[];    //segment tree

    public static void main(String args[])throws Exception
    {
        FastReader bu=new FastReader();
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb=new StringBuilder();
        n=bu.nextInt(); q=bu.nextInt();
        st=new Node[n<<2];
        build(1,0,n-1);

        while(q-->0)
        {
            int op=bu.nextInt(),x=bu.nextInt(),y=bu.nextInt();
            if(op==0) update(1,0,n-1,x,y);
            else bw.write(query(1,0,n-1,x,y)+"\n");
        }
        bw.flush();
    }

    static class Node
    {
        int three,two,one,lazy;
        Node()
        {
            three=two=one=lazy=0;
        }
    }

    static void build(int i,int l,int r)
    {
        st[i]=new Node();
        if(l==r) st[i].three=1;
        else
        {
            int p=i<<1,mid=(l+r)>>1;
            build(p,l,mid);
            build(p+1,mid+1,r);
            st[i].three=st[p].three+st[p+1].three;
        }
    }

    static void propagate(int i,int l,int r)
    {
        if(l!=r)
        {
            int p=i<<1;
            st[p].lazy+=st[i].lazy;
            st[p+1].lazy+=st[i].lazy;
        }
        st[i].lazy%=3;

        if(st[i].lazy==1)
        {
            int t=st[i].three;
            st[i].three=st[i].one;
            st[i].one=st[i].two;
            st[i].two=t;
        }
        else if(st[i].lazy==2)
        {
            int t=st[i].three;
            st[i].three=st[i].two;
            st[i].two=st[i].one;
            st[i].one=t;
        }
        st[i].lazy=0;
    }

    static void update(int i,int l,int r,int x,int y)
    {
        propagate(i,l,r);
        if(l>=x && r<=y)
        {
            st[i].lazy++;
            propagate(i,l,r);
            return;
        }
        else if(l>y || r<x) return;
        else
        {
            int p=i<<1, mid=(l+r)>>1;
            update(p,l,mid,x,y);
            update(p+1,mid+1,r,x,y);
            st[i].three=st[p].three+st[p+1].three;
            st[i].two=st[p].two+st[p+1].two;
            st[i].one=st[p].one+st[p+1].one;
        }
    }

    static int query(int i,int l, int r,int x,int y)
    {
        propagate(i,l,r);
        if(l>y || r<x) return 0;
        else if(l>=x && r<=y) return st[i].three;
        int p=i<<1,mid=(l+r)>>1;
        return query(p,l,mid,x,y)+query(p+1,mid+1,r,x,y);
    }

    static class FastReader
    {
        final private int BUFFER_SIZE=1<<16;
        private DataInputStream dis;
        private byte[] buffer;
        private int bufferPointer,bytesRead;

        public FastReader() 
        {
            dis=new DataInputStream(System.in);
            buffer=new byte[BUFFER_SIZE];
            bufferPointer=bytesRead=0;
        }
        
        public int nextInt() throws IOException 
        {
            int ret=0;
            byte c=read();
            while(c<=' ') c=read();
            boolean neg=(c=='-');
            if(neg) c=read();
            do 
            {
                ret=ret*10+c-'0';
            }while((c=read())>='0' && c<='9');
            if(neg) return -ret;
            return ret;
        }
        
        private void fillBuffer()throws IOException 
        {
            bytesRead=dis.read(buffer,bufferPointer=0,BUFFER_SIZE);
            if(bytesRead==-1) buffer[0]=-1;
        }
        private byte read() throws IOException 
        {
            if(bufferPointer==bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
    }
}

Disclaimer: The above Problem (Multiples of 3) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.

Leave a Comment

Your email address will not be published.