Technique please

In byterace contest(rated for div2) there was a question where my though process was right but cant avoid TLE can anybody tell me that technique… link of question is below

keep account of how much a query has traveled for each given i.

ll n,q;
cin>>n>>q;
vector<pll> v;
foi(q){
	ll l,r;
	cin>>l>>r;
	l-=1;r-=1;
	v.pb({l,r});
}
unordered_map<ll,vll> m,m2;
foi(q) m[v[i].ff].pb(v[i].ss);
foi(q) m2[v[i].ss].pb(v[i].ff);

ll curr=0; //value of current index
ll adder=0;  //sum that we need to add to curr at each iteration, Depends upon the number of queries in-processing and how much they have been already processed.
foi(n){
	ll add=m[i].size()>0?m[i].size():0;   //add=no. of new queries at index i
	adder+=add;                                    //update adder
	adder-=m2[i-1].size();                    //remove queries that ended at i-1
	if(i!=0&&m2[i-1].size()>0){            
		for(auto it:m2[i-1]){              //traverse the queries that ended at i-1
			curr-=(i-t);                      //remove their values from our curr variable
		}
	}
	curr+=adder;                //update current
	cout<<curr<<" ";
}
cout<<endl;

bro your code has too many macros can you explain without code

It will be bit lengthy for me to explain as i am not good at explaining approaches by text. So, maybe you can wait for editorial where they will give you detailed solution with intuition behind it.

can anyone check my code

https://www.codechef.com/viewsolution/40944002

okk bro and thx for your help i’ll try to understan :relaxed:d

i dont know this language

This is C++ only :sweat_smile:

never saw something like this before :upside_down_face:

Self explaining code. I just used difference array for range update AP in O(1).

t = int(input())
for _ in range(t):
    n,q = map(int,input().split())
    a = [0]*(n+1)
    b = [0]*(n+1)
    for i in range(q):
        l,r = map(int,input().split())
        m = r-l+1
        l-=1
        r-=1
        a[l]+=1
        a[r+1]-=1+m
        b[l]+=1
        b[r+1]-=1
    sm = 0
    res = []
    for i in range(n):
        res.append(a[i]+sm)
        sm+=b[i]
    for i in range(1,n):
        res[i]+=res[i-1]
    print(*res)

Say if you want me to explain more about it.

can you please check my code for cab

https://www.codechef.com/viewsolution/40944002

Your logic seems correct but implementation is wrong. Suppose you get your a=[1,2,4] and you are transforming it for n = 7 then your implementation will transform it to [1,1,1,1,2,1] but for correct answer it should transform into [1,1,1,1,1,1,1]

You can use Max Heap for implementation. (In python by default there is only Min Heap, I used negative values to use it as Max heap)

Here is my implementation.

from heapq import heapify, heappop, heappush
for _ in range(int(input())):
    n,k = map(int,input().split())
    a = []
    for i in range(26):
        if (k>>i)&1:
            a.append(-i)
    heapify(a)
    while len(a)<n:
        x = -heappop(a)
        if x==0:  break
        y = x-1
        heappush(a, -y)
        heappush(a, -y)
    if len(a)!=n:
        print(-1); continue
    res = []
    s = "abcdefghijklmnopqrstuvwxyz"
    for i in a:
        res.append(s[-i])
    print("".join(res))