AtCoder Beginner Contest 260 - C, D, E

https://atcoder.jp/contests/abc260/tasks

E - At Least One

The question
Given $N$ Pairs of numbers $\left(A_1,B_1\right),\left(A_2,B_2\right),\dots ,\left(A_N,B_N\right)$
For all $i$, All satisfied with $1\le A_i<B_i\le M$.

If in a continuous interval $[l,r]$ in ,$N$ The number is right $A_i$ and $B_i$ There is at least one , So this continuous interval is Good interval .

ask , The length is $1,2,...,M$ Of Good interval How many of them are there ？

• $1\le N\le 2\times 10^5$
• $2\le M\le 2\times 10^5$
• $1\le A_i<B_i\le M$

Ideas
Will number i Are hung separately Ai and Bi below , That is, for a number , It corresponds to multiple numbers , altogether M Number .
If a continuous number , Satisfy n All numbers have appeared , Then this number is good .

If a good interval is determined from l To r, Then its outward extension range is also good .

Traverse each position from front to back i, You can use the sliding window to maintain the minimum satisfied interval every time [l, r], Then the length of this interval is the shortest interval , And all the intervals that extend to the left and right of this interval are satisfied .

To prevent interval repetition , This interval only extends to the left , It is satisfied to extend to the first position .

in other words , length r-l+1 To length i The interval length of is satisfied , The number of answers of these lengths is +1（ Differential realization ）.

All in all M A place , Each number can enter and leave the team at most twice , The total complexity is $O(N+M)$.

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], ans[N];
int q[N], mp[N];
vector<int> v[N];

bool check(int i)
{
    
	for(int x : v[i])
	{
    
		if(mp[x] == 1) return 0;
	}
	return 1;
}

signed main(){
    
	Ios;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
    
		int x, y; cin >> x >> y;
		v[x].push_back(i);
		v[y].push_back(i);
	}
	
	int sum = 0;
	int hh = 0, tt = -1;
	for(int i=1;i<=m;i++)
	{
    
		q[++tt] = i;
		for(int x : v[i]){
    
			mp[x]++;
			if(mp[x] == 1) sum++;
		}
		while(hh <= tt && check(q[hh])){
    
			for(int x : v[q[hh]]) mp[x]--;
			hh++;
		}
		if(sum == n) ans[tt-hh+1]++, ans[i+1]--;
	}
	for(int i=1;i<=m;i++) ans[i] += ans[i-1], cout << ans[i] << " ";
	
	return 0;
}

D - Draw Your Cards

The question
Yes N The opposite card , Each card has value $X_i$, Different from each other .
Take one from the top each time , Assuming that X, Put it in the pile of cards that have been removed .

• Find the first card on the top of all stacks that is greater than or equal to X The card of , Put it on it .
• If you can't find it, make another pile .
• If the number of cards in a deck equals K 了 , Then this stack of cards will be cleared .

ask , Each card is cleared after several card taking operations ？ If not cleared , Output -1.

$1\le K\le N\le 2\times 10^5$

Ideas
Just simulate according to the meaning of the title , You can number the existing deck , Then record the stack number of each card taken out .
Put the top card on set in , It is convenient for two points to find the corresponding stack .

Be careful K = 1 The situation of .

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
vector<int> v[N];
int pos[N], ans[N];

signed main(){
    
	Ios;
	cin >> n >> m;
	
	set<int> st;
	int cnt = 0;
	for(int i=1;i<=n;i++)
	{
    
		int x; cin >> x;
		auto it = st.lower_bound(x);
		if(it != st.end())
		{
    
			int tx = *it;
			pos[x] = pos[tx];
			st.erase(tx);
			v[pos[tx]].push_back(x);
			if(v[pos[tx]].size() == m)
			{
    
				for(int t : v[pos[tx]])
					ans[t] = i;
			}
			else st.insert(x);
		}
		else{
    
			pos[x] = ++cnt;
			v[cnt].push_back(x);
			
			if(m == 1) ans[x] = i;
			else st.insert(x);
		}
	}
	
	for(int i=1;i<=n;i++)
		if(ans[i]) cout << ans[i] << "\n";
		else cout << "-1\n";
	
	return 0;
}

C - Changing Jewels

The question
Given X, Y And a grade of n Ruby .
ask , After the following transformation , The maximum level you can get is 1 Sapphire ？

• $redn\to red(n-1)+X\ast bluen$;
• $bluen\to red(n-1)+Y\ast blue(n-1)$;

$1\le n\le 10$, $1<X<5$, $1\le Y\le 5$

Ideas
Direct two recursions to engage with each other RE 了 ..

Then take all blue n All of them are transformed first , All become red and The last number , Then a recursive red That's it .

From the second transformation ：
$bluen\to red(n-1)+Y\ast red(n-2)+Y^2\ast red(n-3)+...+Y^{n-1}$

that
$redn\to red(n-1)+X\ast [red(n-1)+Y\ast red(n-2)+Y^2\ast red(n-3)+...+Y^{n-1}]$.

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];
int x,y;

int red(int n)
{
    
	if(n < 2) return 0;
	
	int sum = 0;
	
	sum += red(n-1);
	
	int cnt = 0;
	for(int i = n-1; i>=0;i--)
	{
    
		sum += x*(pow(y, cnt++) * red(i));
	}
	sum += x * pow(y, n-1);
	
	return sum;
}

signed main(){
    
	Ios;
	cin >> n >> x >> y;
	
	cout << red(n);
	
	return 0;
}