Codeworks 5 questions per day (1700 average) - day 5

Report

Topic translation

Given n A sequence of integers and m Operations , Given by each operation ti and ri, There are two kinds of operations ：

• ti by 1, Then the front ri The number is in continuous and undiminished order （ From small to large ） array ;
• ti by 2, Then the front ri The number is in continuous non increasing order （ From big to small ） array .

seek m Sequence after operation .

Title Description

Each month Blake gets the report containing main economic indicators of the company “Blake Technologies”.

There are n commodities produced by the company.

For each of them there is exactly one integer in the final report, that denotes corresponding revenue.

Before the report gets to Blake, it passes through the hands of m managers.

Each of them may reorder the elements in some order.

Namely, the i -th manager either sorts first r_{i} numbers in non-descending or non-ascending order and then passes the report to the manager i+1 , or directly to Blake (if this manager has number i=m ).

Employees of the “Blake Technologies” are preparing the report right now.

You know the initial sequence a_{i} of length n and the description of each manager, that is value r_{i} and his favourite order.

You are asked to speed up the process and determine how the final report will look like.

Input format

The first line of the input contains two integers n and m ( 1<=n,m<=200000 ) — the number of commodities in the report and the number of managers, respectively.

The second line contains n integers a_{i} ( |a_{i}|<=10^{9} ) — the initial report before it gets to the first manager.

Then follow m lines with the descriptions of the operations managers are going to perform.

The i -th of these lines contains two integers t_{i} and r_{i} (, 1<=r_{i}<=n ), meaning that the i -th manager sorts the first r_{i} numbers either in the non-descending (if t_{i}=1 ) or non-ascending (if t_{i}=2 ) order.

Output format

Print n integers — the final report, which will be passed to Blake by manager number m .

Examples #1

The sample input #1

3 1
1 2 3
2 2

Sample output #1

2 1 3

Examples #2

The sample input #2

4 2
1 2 4 3
2 3
1 2

Sample output #2

2 4 1 3

Tips

In the first sample, the initial report looked like: 1 2 3.

After the first manager the first two numbers were transposed: 2 1 3.

The report got to Blake in this form.

In the second sample the original report was like this: 1 2 4 3.

After the first manager the report changed to: 4 2 1 3.

After the second manager the report changed to: 2 4 1 3.

This report was handed over to Blake.

#include<bits/stdc++.h>
using namespace std; 
const int N=3e5+5;
typedef long long ll;
int n,a[N],id[N],tt[N],m,t,r,mmax=0,s[N];
int main(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
    
		scanf("%d %d",&t,&r);
		id[r]=i;
		tt[r]=t;
		mmax=max(mmax,r);
	}
	sort(a+1,a+1+mmax);
	int shun=mmax,dao=1,k=0,kk;
	for(int i=mmax;i;i--){
    
		if(k<id[i]){
    
			k=id[i];
			kk=tt[i];
		}
		if(kk==1){
    
			s[i]=a[shun--];
		}
		else{
    
			s[i]=a[dao++];
		}
	}
	for(int i=1;i<=mmax;i++){
    
		cout<<s[i]<<" ";
	}
   for(int i=mmax+1;i<=n;i++){
    
   		cout<<a[i]<<" ";
   }
	return 0;
}

Processing Queries

Topic translation

Problem description

There is a single threaded production line , That is, only one job can be handled at the same time , Yes $n$ Job applications , The first $i$ The start time of work is $t_i$, It needs to be done $d_i$ Unit time , be-all $t_i$ Are different .

When a job application appears , The production line will have the following three treatment schemes ：

1. If the production line is idle , And the waiting queue is empty , Then the currently applied work will be executed immediately .
2. If the production line is working , And the work in the waiting queue is less than $b$ individual , Then the currently applied work will be added to the end of the waiting queue .
3. If the production line is working , And there are already jobs waiting in the queue $b$ individual , The job you are currently applying for will be rejected , And I will never accept the application for the job again .

I / O format

Input format

first line , Two integers $n$ and $b$.

Next $n$ That's ok , Two integers per line $t_i$ and $d_i$.

Output format

The output is one line , contain $n$ It's an integer , Sequential representation $n$ Completion time of work , If the current work is rejected, output $-1$.

explain / Tips

$1\le n,b\le 2\times 10^5$.

$1\le t_i,d_i\le 10^9$.

$t_{i-1}<t_i$.

Title Description

In this problem you have to simulate the workflow of one-thread server.

There are n queries to process, the i -th will be received at moment t_{i} and needs to be processed for d_{i} units of time.

All t_{i} are guaranteed to be distinct.

When a query appears server may react in three possible ways:

1. If server is free and query queue is empty, then server immediately starts to process this query.
2. If server is busy and there are less than b queries in the queue, then new query is added to the end of the queue.
3. If server is busy and there are already b queries pending in the queue, then new query is just rejected and will never be processed.

As soon as server finished to process some query, it picks new one from the queue (if it’s not empty, of course).

If a new query comes at some moment x , and the server finishes to process another query at exactly the same moment, we consider that first query is picked from the queue and only then new query appears.

For each query find the moment when the server will finish to process it or print -1 if this query will be rejected.

Input format

The first line of the input contains two integers n and b ( 1<=n,b<=200000 ) — the number of queries and the maximum possible size of the query queue.

Then follow n lines with queries descriptions (in chronological order).

Each description consists of two integers t_{i} and d_{i} ( 1<=t_{i},d_{i}<=10^{9} ), where t_{i} is the moment of time when the i -th query appears and d_{i} is the time server needs to process it.

It is guaranteed that t_{i-1}<t_{i} for all i>1 .

Output format

Print the sequence of n integers e_{1},e_{2},…,e_{n} , where e_{i} is the moment the server will finish to process the i -th query (queries are numbered in the order they appear in the input) or -1 if the corresponding query will be rejected.

Examples #1

The sample input #1

5 1
2 9
4 8
10 9
15 2
19 1

Sample output #1

11 19 -1 21 22

Examples #2

The sample input #2

4 1
2 8
4 8
10 9
15 2

Sample output #2

10 18 27 -1

Tips

Consider the first sample.

1. The server will start to process first query at the moment 2 and will finish to process it at the moment 11 .
2. At the moment 4 second query appears and proceeds to the queue.
3. At the moment 10 third query appears. However, the server is still busy with query 1 , b=1 and there is already query 2 pending in the queue, so third query is just rejected.
4. At the moment 11 server will finish to process first query and will take the second query from the queue.
5. At the moment 15 fourth query appears. As the server is currently busy it proceeds to the queue.
6. At the moment 19 two events occur simultaneously: server finishes to proceed the second query and the fifth query appears. As was said in the statement above, first server will finish to process the second query, then it will pick the fourth query from the queue and only then will the fifth query appear. As the queue is empty fifth query is proceed there.
7. Server finishes to process query number 4 at the moment 21 . Query number 5 is picked from the queue.
8. Server finishes to process query number 5 at the moment 22 .

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+5;
typedef long long ll;
ll n,b,t[N],d[N],tt;
queue<ll> s;
int main(){
    
	cin>>n>>b;
	for(int i=1;i<=n;i++){
    
		scanf("%lld %lld",&t[i],&d[i]);
	}
	tt=t[1]+d[1];
	cout<<tt<<" ";
	s.push(tt);
	for(int i=2;i<=n;i++){
    
		while(!s.empty()&&s.front()<=t[i]){
    
			s.pop();
		}
		if(s.size()<=b){
    
			tt=max(tt,t[i]);
			tt+=d[i];
			printf("%lld ",tt);
			s.push(tt);
		}
		else{
    
			printf("-1 ");
		}
	}
	return 0;
}

Correct Bracket Sequence Editor

Topic translation

Title Description

Polycarp There is a length of $n$ Bracket string of .

We set up $pr{e}_i$ Is the second in the string $1$ Position to the first $i$ The number of left parentheses minus the number of right parentheses , Then when everyone $1⩽i⩽n$ , $pr{e}_i⩾0$ . meanwhile $pr{e}_n=0$ when , We think this bracket string is legal .

Now? Polycarp An editor is designed for legal bracket strings , This editor supports the following operations :

1. L, Move the cursor to the left one space
2. R, Move the cursor to the right one space
3. D, Delete all characters from this bracket to its corresponding bracket , After deletion , The cursor will jump to the leftmost bracket on its right that has not been deleted , If there are no such brackets , Then the cursor will jump to the rightmost bracket on its left that has not been deleted .

for instance :

Above picture , Use the string on the left of the first row D, bring $[2,3]$ All deleted .

In the second row , Use D, Deleted $[4,7]$ , Because the first $7$ Pairs of parentheses are in $4$ It's about .

The same is true of the third row .

Polycarp The editor of does not support wrong operations , For example, delete the entire string .

Polycarp Proud of his design , But he will not implement this editor , So he wants you to help him realize , Can you help him realize the function of editor ？

Input format

There are three lines of input .

first line , Three integers $n,m,p$ , Respectively represents the length of the bracket string , The number of operations and the initial position of the cursor .

The second line , A length of $n$ Bracket string of .

The third line , A length of $m$ String , Represents the sequence of operations .

Output format

The output is one line .

first line , A string of parentheses . Indicates that the original bracket string has been $m$ Bracket string after operation .

Data range

$1⩽p⩽n⩽5\times 10^5,1⩽m⩽5\times 10^5$

Title Description

Recently Polycarp started to develop a text editor that works only with correct bracket sequences (abbreviated as CBS).

Note that a bracket sequence is correct if it is possible to get a correct mathematical expression by adding “+”-s and “1”-s to it. For example, sequences “(())()”, “()” and “(()(()))” are correct, while “)(”, “(()” and “(()))(” are not. Each bracket in CBS has a pair. For example, in “(()(()))”:

• 1st bracket is paired with 8th,
• 2d bracket is paired with 3d,
• 3d bracket is paired with 2d,
• 4th bracket is paired with 7th,
• 5th bracket is paired with 6th,
• 6th bracket is paired with 5th,
• 7th bracket is paired with 4th,
• 8th bracket is paired with 1st.

Polycarp’s editor currently supports only three operations during the use of CBS. The cursor in the editor takes the whole position of one of the brackets (not the position between the brackets!). There are three operations being supported:

• «L» — move the cursor one position to the left,
• «R» — move the cursor one position to the right,
• «D» — delete the bracket in which the cursor is located, delete the bracket it’s paired to and all brackets between them (that is, delete a substring between the bracket in which the cursor is located and the one it’s paired to).

After the operation “D” the cursor moves to the nearest bracket to the right (of course, among the non-deleted). If there is no such bracket (that is, the suffix of the CBS was deleted), then the cursor moves to the nearest bracket to the left (of course, among the non-deleted).

There are pictures illustrated several usages of operation “D” below.

All incorrect operations (shift cursor over the end of CBS, delete the whole CBS, etc.) are not supported by Polycarp’s editor.

Polycarp is very proud of his development, can you implement the functionality of his editor?

Input format

The first line contains three positive integers n , m and p ( 2<=n<=500000 , 1<=m<=500000 , 1<=p<=n ) — the number of brackets in the correct bracket sequence, the number of operations and the initial position of cursor.

Positions in the sequence are numbered from left to right, starting from one. It is guaranteed that n is even.

It is followed by the string of n characters “(” and “)” forming the correct bracket sequence.

Then follow a string of $ m $ characters “L”, “R” and “D” — a sequence of the operations.

Operations are carried out one by one from the first to the last.

It is guaranteed that the given operations never move the cursor outside the bracket sequence, as well as the fact that after all operations a bracket sequence will be non-empty.

Output format

Print the correct bracket sequence, obtained as a result of applying all operations to the initial sequence.

Examples #1

The sample input #1

8 4 5
(())()()
RDLD

Sample output #1

()

Examples #2

The sample input #2

12 5 3
((()())(()))
RRDLD

Sample output #2

(()(()))

Examples #3

The sample input #3

8 8 8
(())()()
LLLLLLDD

Sample output #3

()()

Tips

In the first sample the cursor is initially at position 5 . Consider actions of the editor:

1. command “R” — the cursor moves to the position 6 on the right;
2. command “D” — the deletion of brackets from the position 5 to the position 6 . After that CBS takes the form (())(), the cursor is at the position 5 ;
3. command “L” — the cursor moves to the position 4 on the left;
4. command “D” — the deletion of brackets from the position 1 to the position 4 . After that CBS takes the form (), the cursor is at the position 1 .

Thus, the answer is equal to ().

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
char a[N],b[N];
struct stu{
    
	int left,right,to;
}s[N];
stack<int> k;
int n,m,p;
int main(){
    
	cin>>n>>m>>p>>a+1>>b;
	for(int i=1;i<=n;i++){
    
		s[i].left=i-1;
		s[i].right=i+1;
		if(a[i]=='(') k.push(i);
		else{
    
			s[i].to=k.top();
			s[k.top()].to=i;
			k.pop();
		}
	}
	int kk=1;
	for(int i=0;i<m;i++){
    
		if(b[i]=='L'){
    
			p=s[p].left;
		}
		else if(b[i]=='R'){
    
				p=s[p].right;
		}
		else{
    
			int l=min(p,s[p].to);
			int r=max(p,s[p].to);
			if(s[r].right!=n+1){
    
				p=s[r].right;
			}
			else p=s[l].left;
			s[s[r].right].left=s[l].left;
			s[s[l].left].right=s[r].right;
			if(l==kk) kk=s[r].right;
		}
	}
	for(int i=kk;i!=n+1;i=s[i].right){
    
		printf("%c",a[i]);
	}
	return 0;
}

Recover Polygon (easy)

Title Description

The zombies are gathering in their secret lair!

Heidi will strike hard to destroy them once and for all.

But there is a little problem… Before she can strike, she needs to know where the lair is.

And the intel she has is not very good.

Heidi knows that the lair can be represented as a rectangle on a lattice, with sides parallel to the axes.

Each vertex of the polygon occupies an integer point on the lattice.

For each cell of the lattice, Heidi can check the level of Zombie Contamination.

This level is an integer between 0 and 4 , equal to the number of corners of the cell that are inside or on the border of the rectangle.

As a test, Heidi wants to check that her Zombie Contamination level checker works.

Given the output of the checker, Heidi wants to know whether it could have been produced by a single non-zero area rectangular-shaped lair (with axis-parallel sides).

Input format

The first line of each test case contains one integer N , the size of the lattice grid ( 5<=N<=50 ).

The next N lines each contain N characters, describing the level of Zombie Contamination of each cell in the lattice.

Every character of every line is a digit between 0 and 4.

Cells are given in the same order as they are shown in the picture above: rows go in the decreasing value of y coordinate, and in one row cells go in the order of increasing x coordinate.

This means that the first row corresponds to cells with coordinates (1,N),…,(N,N) and the last row corresponds to cells with coordinates (1,1),…,(N,1) .

Output format

The first line of the output should contain Yes if there exists a single non-zero area rectangular lair with corners on the grid for which checking the levels of Zombie Contamination gives the results given in the input, and No otherwise.

Examples #1

The sample input #1

6
000000
000000
012100
024200
012100
000000

Sample output #1

Yes

Tips

The lair, if it exists, has to be rectangular (that is, have corners at some grid points with coordinates (x_{1},y_{1}) , (x_{1},y_{2}) , (x_{2},y_{1}) , (x_{2},y_{2}) ), has a non-zero area and be contained inside of the grid (that is, 0<=x_{1}<x_{2}<=N , 0<=y_{1}<y_{2}<=N ), and result in the levels of Zombie Contamination as reported in the input.

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
int a[100][100],n;
int p[4][2]={
    1,1,1,-1,-1,1,-1,-1};
int main(){
    
	cin>>n;
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<=n;j++){
    
			scanf("%1d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
    
		for(int j=1;j<=n;j++){
    
			if(a[i][j]==0){
    
				continue;
			}
			int k=0;
			for(int kk=0;kk<4;kk++){
    
				if(a[i+p[kk][0]][j+p[kk][1]]) k++;
			}
			if(a[i][j]!=k){
    
				puts("No");
				return 0;
			}
		}
	}
	puts("Yes");
	return 0;
}

Sea Battle

Topic translation

Yes $n$ Lattice , It contains $a$ Ships , Per ship $b$ Lattice , But I don't know the location of the ship . Galya Shot at these squares $k$ Time , Unfortunately, the ship was not shot ,
Now give a length of $n$ String , among $0$ Represents an unknown lattice , $1$ It means that it has been shot and confirmed that there is no ship in the grid , Ask to shoot at least one ship , How many more shots are needed , And output the number of these positions .

thank @ Lingyou Translation provided

Title Description

Galya is playing one-dimensional Sea Battle on a 1×n grid.

In this game a ships are placed on the grid.

Each of the ships consists of b consecutive cells.

No cell can be part of two ships, however, the ships can touch each other.

Galya doesn’t know the ships location.

She can shoot to some cells and after each shot she is told if that cell was a part of some ship (this case is called “hit”) or not (this case is called “miss”).

Galya has already made $ k $ shots, all of them were misses.

Your task is to calculate the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

It is guaranteed that there is at least one valid ships placement.

Input format

The first line contains four positive integers n , a , b , k ( 1<=n<=2·10^{5} , 1<=a,b<=n , 0<=k<=n-1 ) — the length of the grid, the number of ships on the grid, the length of each ship and the number of shots Galya has already made.

The second line contains a string of length n , consisting of zeros and ones. If the i -th character is one, Galya has already made a shot to this cell.

Otherwise, she hasn’t. It is guaranteed that there are exactly k ones in this string.

Output format

In the first line print the minimum number of cells such that if Galya shoot at all of them, she would hit at least one ship.

In the second line print the cells Galya should shoot at.

Each cell should be printed exactly once.

You can print the cells in arbitrary order.

The cells are numbered from 1 to n , starting from the left.

If there are multiple answers, you can print any of them.

Examples #1

The sample input #1

5 1 2 1
00100

Sample output #1

2
4 2

Examples #2

The sample input #2

13 3 2 3
1000000010001

Sample output #2

2
7 11

Tips

There is one ship in the first sample.

It can be either to the left or to the right from the shot Galya has already made (the “1” character).

So, it is necessary to make two shots: one at the left part, and one at the right part.

#include<bits/stdc++.h>
using namespace std; 
const int N=5e5+5;
typedef long long ll;
int n,a,b,k,p=0,ss=0;
int xs[N];
string s;
int main(){
    
	cin>>n>>a>>b>>k>>s;
	for(int i=0;i<n;i++){
    
		if(s[i]=='0'){
    
			p++;
			if(p==b){
    
				p=0;
				ss++;
				xs[ss]=i+1;
			}
		}
		if(s[i]=='1') p=0;
	}
	ss-=a-1;
	cout<<ss<<endl;
	for(int i=1;i<=ss;i++){
    
		cout<<xs[i]<<" ";
	}
	return 0;
}