I was solving 446C - DZY любит числа Фибоначчи today where it's needed to add geometric sequence to the segment but the ratio is always the same. So I was wondering how to solve the problem where we are given queries of type $$$L,R,A,B$$$ and we need to add geometric sequence $$$A,AB,AB^2,AB^3,... AB^{R-L}$$$ to the segment $$$[L,R]$$$? There is also a sum query for some range.

I've been solving 1311C - Выполни комбо and when i used memset I received TLE 73574138 but when I changed to iterative method I received AC 73575826. This is not the first time happening. What the reason behind this?

I'm preparing for Team Selection Competition and these are some problems that I want to know how to solve. Problems are from previous competitions

Given N, М and K. All nubers are  <  = 10⁹
Define value of matrix in row i and column j as (i + j) mod K where i <  = N and j <  = M

Given Q <  = 2 * 10⁵ queries of form Li, Lj, Ri, Rj and you need to find sum of elements in submatrix with upper left corner (Li, Lj) and lower right corner (Ri, Rj) module 10⁹ + 7.

Some ideas?

Given string S of N (N<=100 000) characters (each character is digit). Also given, L and R (L <= R <= 10⁹ ). Find maximum sum that is possible to obtain cutting the string in such a way that every part has value <=R and >=L.

Input: N L R S

Test case:
8 13 997
81196054

Output: 1825

Explanation: These are all possible cuts. Last cut is best
1. 81|19|60|54
2. 81|196|054
3. 811|96|054
4. 811|960|54

List of integers is formed such that all integers that can be written in form 2^x3^y5^z are sorted in increasing order. So, list look like this: 1, 2, 3, 4, 5, 6, 8, 9, ... What is n-th element (0-indexed) in list?
0 <  = n <  = 10⁵

Input
500
Output
944784

What is the idea behind this problem?

Link to the problem

Given array A of N elements. We are allowed to do one operation: merge two elements A[i] and A[i+1] into A[i]+A[i+1]. We need to find sequence of exactly K elements with maximum possible GCD.

1 <= K < N <= 10^5
A[i] <= 10^6
sum of all A[i]'s <= 10^6

Input: 6 3
12 7 3 2 15 15

Output:
6
12 12 30

Given array of N elements. Find number of coprime pairs.

1 <= N <= 30000
1 <= A[i] <= 10^8

TL: 0.6s
ML: 64MB

Given convex polygon with N points (clockwise and there are no 3 collinear points). Also given M vertical line segments. Find out how many edges of polygon are intersected by at least one line segment.
Note that if line segment is going through one of the N points, then both edges are counting.

Points are represented as Xi Yi.
Line segments are represented as Ai Pi Ki which means that starting point is at (Ai,Pi) and ending point is at (Ai,Ki)

3 <= N <= 10^5
1 <= M <= 10^5
-10^7 <= Xi,Yi,Ai,Pi,Ki <= 10^7
TL: 1s
ML: 64MB

Given graph with N vertices and M edges. You need to find if there is a way to partition the graph in two parts in such a way that these parts are connected with at least m/2 edges. Division is integer division. If there is solution print it out, else print -1. Input: first two numbers are N and M. Next M lines are pairs of integers (X,Y) representing edge between vertices X and Y. Output: If there is no solution, print -1. Else, in the first line print size of two groups (N1,N2) , in second line print N1 numbers representing vertices in first group, same for second group.

5<= N <= 1000
1<= M <= 10000
TL : 0.2s
ML : 64MB

Input:
8 10
1 2
1 5
1 6
5 6
2 6
3 8
3 7
3 4
4 8
7 8

Output:
4 4
5 6 7 8
1 2 3 4

Your help would be appreciated.

Given N. We can make equality with K numbers (can be repeated) like this:

(a1+1)*(a2+1)*...(aK+1) = N*a1*a2*...*aK

Find the smallest possible value of K for which there are integers that satisfy above equality

Sample 1: Input:4 --> Output:2 --> Explanation: Integers a1 = 1 and a2 = 1 are satisfying equation.

2 < n < 1000 TL: 0.1s ML: 64MB

I thought that the answer is phi(n), but that's just a guess.

I was doing one problem and thought of maximum number of divisors. What I want to say is : We iterate from 1 to N (N<=10^9) and define S(i) number of divisors of number i. What is maximum S we can get? I think it is about 100 or maybe less but if someone can prove.

Given two arrays A and B of size N. Let's take A={4,2,8} AND B={2,7,3}. All possible absolute values are 1: |4-2|+|4-7|+|4-3|=6 ; 2: |2-2|+|2-7|+|2-3|=6 ; 3: |8-2|+|8-7|+|8-3|=12; Sum of all these is 6+6+12=24;

Constraints : 1<=N<=10^5 , |Ai|,|Bi|<=10^6, so Ai,Bi can be negative

Any help with solution with time complexity O(nlogn)?