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.
okk bro and thx for your help i’ll try to understan d
i dont know this language
This is C++ only
never saw something like this before
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.
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))