Topic & Translation

Problem solution

although m m m is big, but n n n is very small, so the title allows us to O ( n m ) O(nm) Solve the problem within O(nm).

Define a dp[i][j]=0/1?
If it is the second i i Can i stop at j j j point, we will find that from the first to the smallest i i i satisfied d p [ i ] [ j ] = 1 dp[i][j]=1 dp[i][j]=1, followed by d p [ i + 1... n ] [ j ] dp[i+1...n][j] dp[i+1...n][j] must be 1, because the following operations can make a = 0 a=0 a=0 and then don't move. So we don't need to define the first dimension at all.

Then define a dp[i] representation to i i Minimum possible operation at i?
We will find that because y i y_i Due to the limitation of yi ， we lack information on the number of times and cannot transfer, so we should record the information at the same time.

Make dp[i][j] Express i i The minimum possible operation when i is satisfied that the operation has been executed at this time j j j times?
In fact, this is ridiculous. First, to i i The minimum possible operation at i is certain, which has nothing to do with the number of executions "j" you force. More strictly speaking, the operand is the cause and the number of executions is the result. You can't put the result into the state. Second, since the minimum operand is determined, the i i i, the fewer times the operation is executed, the better.

Therefore, we define (pair < int, int >) DP [i], and the first value represents to i i The minimum possible operation at i, and the second value represents to i i Minimum number of executions at i.
At this time, the smaller of the two pair s is just to compare the first and then the second.
For convenience N e x t i ( k ) {\rm Next}_i(k) Nexti (k) indicates the slave position k k k start, execute once i i The position reached after class i operation is transferred as follows:

1. { d p [ i ] . f i r s t , d p [ i ] . s e c o n d + 1 } → d p [ N e x t d p [ i ] . f i r s t ( i ) ] \{dp[i].{\rm first},dp[i].{\rm second}+1\}\rightarrow dp[{\rm Next}_{dp[i].{\rm first}}(i)] {dp[i].first,dp[i].second+1}→dp[Nextdp[i].first​(i)]
2. { j , 1 } → d p [ N e x t j ( i ) ] \{j,1\}\rightarrow dp[{\rm Next}_{j}(i)] {j,1}→dp[Nextj​(i)]

The condition of the first transfer is that the execution times are not reached y y The restriction of y, the second transfer condition is j j j is greater than the current d p [ i ] . f i r s t dp[i].{\rm first} dp[i].first.

Number of States O ( m ) O(m) O(m), transition complexity O ( n ) O(n) O(n), total complexity O ( n m ) O(nm) O(nm).

CODE

#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100005
#define ENDL putchar('\n')
#define LL long long
#define DB double
#define lowbit(x) ((-x) & (x))
#define int LL
LL read() {
	LL f = 1,x = 0;char s = getchar();
	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}
	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}
	return f * x;
}
int n,m,i,j,s,o,k;
int ti[MAXN],yy[MAXN];
LL xx[MAXN];
int tm[MAXN],ai[MAXN];
void add(int i,int tim,int Ai) {
	if(i < 1 || i > n) return ;
	if(tim < tm[i]) tm[i]=tim,ai[i]=Ai;
	else if(tim == tm[i]) ai[i] = min(ai[i],Ai);
//	printf("  %d : %d,%d\n",i,tm[i],ai[i]);
	return ;
}
int adnm(LL x,int i) {return (x+100000ll*i+99999ll)/100000;}
int munm(LL x,int i) {return (x*i+99999ll)/100000;}
signed main() {
	m = read();n = read();
	for(int i = 1;i <= m;i ++) {
		ti[i] = read();
		xx[i] = read();
		yy[i] = read();
	}
	for(int i = 1;i <= n;i ++) tm[i] = 0x3f3f3f3f;
	tm[0] = 0; ai[0] = 0;
	for(int i = 0;i <= n;i ++) {
		if(i > 0) printf("%lld ",tm[i] >= 0x3f3f3f3f ? -1:tm[i]);
		if(tm[i] < 0x3f3f3f3f) {
			int t = tm[i];
			if(ti[t] == 1 && ai[i] < yy[t]) add(adnm(xx[t],i),t,ai[i]+1);
			else if(ti[t] == 2 && ai[i] < yy[t]) add(munm(xx[t],i),t,ai[i]+1);
			for(int j = t+1;j <= m;j ++) {
				if(ti[j] == 1) add(adnm(xx[j],i),j,1);
				else if(ti[j] == 2) add(munm(xx[j],i),j,1);
			}
		}
	}ENDL;
	return 0;
}