Let's store the last moment when somebody gets a tea in the variable $$$lst$$$. Then if for the $$$i-th$$$ student $$$lst ≥ ri$$$ then he will not get a tea. Otherwise he will get it during max($$$lst$$$ + 1, $$$l_i$$$) second. And if he gets a tea then $$$lst$$$ will be replaced with the answer for this student.

[submission:159713776]

• Approach 1:
  Let's use STL function std::lower_bound() to solve this problem. First make vector of pair of <Total_Damage,Time_Stamp> and then use the lower_bound() function to find the smallest Total Damage just greater than or equal to $$$c_j$$$ and then print the Time Stamp corresponding to that damage. Reference for lower_bound() function
  Time Complexity: $$$O(n+m\cdot log(n))$$$
  NOTE: This problem could have been solved using binary search but wasn't needed since you know STL.

• Approach 2:
  First sort the $$$c$$$ array using std::sort() function (in $$$O(m\cdot log(m))$$$ time) and then iterate through $$$c$$$. Once you find the smallest damage $$$a_i >= c_j$$$ then you know that that $$$c_{j+1} >= a_i$$$. Use this fact to solve the question in $$$O(n+m)$$$ (after sorting) time.
  Time Complexity: $$$O(n+m\cdot log(m))$$$

[submission:160223611]

Use stacks to maintain the current state. If the top 2 elements of the stack are the same at a particular instant, then remove those two elements. Keep doing this until you find an unequal pair or stack becomes empty.

[submission:159716108]

Let's denote $$$A(l, r)$$$ as some stack-sortable array which contains all integers from $$$l$$$ to $$$r$$$ (inclusive).

We can see that if the first element of $$$A(l, r)$$$ is $$$x$$$, then $$$A(l, r) = [x] + A(l, x - 1) + A(x + 1, r)$$$, where by  +  we mean concatenation of arrays. It's easy to prove this fact: if the first element is x, then we have to store it in the stack until we have processed all elements less than $$$x$$$, so in $$$A(l, r)$$$ no element that is greater than $$$x$$$ can precede any element less than $$$x$$$.

This way we can represent the prefix we are given. For example, if $$$n = 7, k = 3$$$ and prefix is $$$[6, 3, 4]$$$, then we can rewrite the permutation we have to obtain as:

$$$A(1, 7) = [6] + A(1, 5) + A(7, 7) = [6] + [3] + A(1, 2) + A(4, 5) + A(7, 7) = [6] + [3] + [1] + A(2, 2) + A(4, 5) + A(7, 7)$$$

So the unknown suffix is a contatenation of some stack-sortable arrays. It's easy to see that if an array is sorted in non-increasing order, then it is stack-sortable. So we can replace each block $$$A(x, y)$$$ with an array $$$[y, y - 1, y - 2, ..., x]$$$.

If during rewriting the given prefix we obtain some impossible situation (for example, when $$$n = 7$$$ and given prefix is $$$[6, 7]$$$, we have $$$[6] + A(1, 5) + A(7, 7)$$$ and $$$7$$$ can't be the beginning of $$$A(1, 5)$$$), then answer is -1.

#include <bits/stdc++.h>
using namespace std; 
 
int main(){
    int n, k; cin >> n >> k;
    
    int A[n], pt = 1; stack<int> stk;
    for (int i = 0; i < n; i++){
        if (i < k) cin >> A[i];
        else A[i] = stk.empty() ? n : stk.top() - 1;
        stk.push(A[i]);
        while (stk.size() and stk.top() == pt) stk.pop(), pt++; 
    }
    
    if (stk.size()) return cout<<-1, 0;
    for (int i : A) cout<<i<<" ";
}

One can notice (or actually derive using some maths) that the answer is the sum of products of nested for loops iterations for every "add" command.

Let's learn to simulate that in linear complexity. Maintain the stack of multipliers: on "for $$$n$$$" push the top of stack multiplied by $$$n$$$ to the stack, on "end" pop the last value, on "add" add the top of the stack to the answer.

The problem, however, is the values are really large. Notice that once you add the value greater or equal to $$$2^{32}$$$ to the answer, it immediately becomes "OVERFLOW!!!". Thus let's push not the real multiplier to the stack but min(multiplier, $$$2^{32}$$$). That way the maximum value you can achieve is about $$$2^{32}\cdot 50000$$$, which fits into the 64-bit integer.

Overall complexity: $$$O(n)$$$.

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < int(n); i++) 

using namespace std;

const long long INF = 1ll << 32;

int main(){
	int l;
	cin >> l;
	
	stack<long long> cur;
	cur.push(1);
	
	long long res = 0;
	forn(_, l){
		string t;
		cin >> t;
		if (t == "for"){
			int x;
			cin >> x;
			cur.push(min(INF, cur.top() * x));
		}
		else if (t == "end"){
			cur.pop();
		}
		else{
			res += cur.top();
		}
	}
	
	if (res >= INF)
		cout << "OVERFLOW!!!" << endl;
	else
		cout << res << endl;
}

Considerr some segment of consecutive equal characters. Let $$$k$$$ be the length of that segment. Easy to see that we should change at least $$$\lfloor \frac{k}{2} \rfloor$$$ characters in the segment to remove all the pairs of equal consecutive letters. On the other hand we can simply change the second, the fourth etc. symbols to letter that is not equal to the letters before and after the segment.

const int N = 200200;

int n;
char s[N];

bool read() {
	if (!gets(s)) return false;
	n = int(strlen(s));
	return true;
}

void solve() {
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n && s[j] == s[i]) j++;
		char c = 'a';
		while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j]))
			c++;
		fore(k, i, j)
			if ((i + k) & 1)
				s[k] = c;
	}
	puts(s);
}

• Approach 1: The fractal is built by a recursive function. Let $$$a$$$ be a square $$$n^k × n^k$$$ result matrix. Write the recursive function fractal(x, y, k) filling a square part of the matrix with an upper left corner in $$$(x, y)$$$ and a length of the side $$$n^k$$$, drawing the fractal of depth $$$k$$$. In case $$$k = 0$$$ put . at the current position. Otherwise you have to divide the part of the matrix into $$$n^2$$$ square parts with size $$$n^{k-1} × n^{k-1}$$$, and fill them according to the model. If the corresponding symbol in the model is *, fill the square with symbols *, otherwise execute fractal(x1, y1, k-1) for $$$(x1, y1)$$$ being the coordinates of the upper left corner of the new square.

• Approach 2: Consider all positions $$$(x, y)$$$. If for some $$$c = n^d$$$, $$$0 ≤ d < k$$$ the square ((x/c)%n, (y/c)%n) of the model is black then $$$(x, y)$$$ must be black, otherwise it is white. It is easy to check that if the square ((x/c)%n, (y/c)%n) is black for $$$d = k - 1$$$, then we have that the current position $$$(x, y)$$$ is in the black square after the first step of the algorithm. If ((x/c)%n, (y/c)%n) is black for $$$d = k - 2$$$, it happens after the second step, etc.

160379640