Submission #104990

#	Time	Username	Problem	Language	Result	Execution time	Memory
104990		antimirage	Lamps (JOI19_lamps)	C++14	6 / 100	1074 ms	31932 KiB

lamp

# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
int n, dp[N][2], pref[N][2];
 
string a, b;
 
inline int calc (int l, int r, int type){
 
	  if (type == 0)
			return pref[r][0] - pref[l - 1][0] + (b[l - 1] == b[l] && b[l] == '0');
 
	  return pref[r][1] - pref[l - 1][1] + (b[l - 1] == b[l] && b[l] == '1');
}

struct st{
	int must, val;
};

st t[3][3][N * 4], t11[N * 4], t10[N * 4];

void push (int i, int j, int v, int tl, int tr)
{
	t[i][j][v].val += t[i][j][v].must;
	
	if (tl != tr){
		t[i][j][v + v].must += t[i][j][v].must;
		t[i][j][v + v + 1].must += t[i][j][v].must;
	}
	t[i][j][v].must = 0;
}

void update (int i, int j, int l, int r, int val, int v = 1, int tl = 0, int tr = n)
{
	push(i, j, v, tl, tr);
	if (l > tr || tl > r) return;
	
	if (l <= tl && tr <= r){
		t[i][j][v].must += val;
		push(i, j, v, tl, tr);
		return;
	}
	int tm = (tl + tr) >> 1;
	
	update(i, j, l, r, val, v + v, tl, tm);
	update(i, j, l, r, val, v + v + 1, tm + 1, tr);
	
	t[i][j][v].val = min( t[i][j][v + v].val, t[i][j][v + v + 1].val );
}
int get (int i, int j, int l, int r, int v = 1, int tl = 0, int tr = n)
{
	push(i, j, v, tl, tr);
	
	if (l > tr || tl > r)
		return 1e9 + 7;
		
	if (l <= tl && tr <= r)
		return t[i][j][v].val;
		
	int tm = (tl + tr) >> 1;
	
	return min( get(i, j, l, r, v + v, tl, tm), get(i, j, l, r, v + v + 1, tm + 1, tr) );
}

main(){
 
	  memset( dp, 0x3f3f3f3f, sizeof(dp) );
 
	  cin >> n >> a >> b;
 
	  a = ' ' + a;
	  b = ' ' + b;
 
	  for (int i = 1; i <= n; i++){
		  
 
			if (b[i] != b[i - 1])
				  pref[i][ b[i] - 48 ] = 1;
 
			pref[i][0] += pref[i - 1][0];
			pref[i][1] += pref[i - 1][1];
	  }
	  dp[0][0] = 0;
	  update( 1, 0, 0, 0, dp[0][1] );
	  update( 1, 1, 0, 0, dp[0][1] );
 
		for (int i = 1; i <= n; i++){
		  
			if (b[i] != b[i - 1] && i - 2 >= 0){
				update(0, b[i] - 48, 0, i - 2, +1);
				update(1, b[i] - 48, 0, i - 2, +1);
			}
			update(0, b[i] - 48, i - 1, i - 1, +1);
			update(1, b[i] - 48, i - 1, i - 1, +1);

			if (a[i] == b[i])
				  dp[i][0] = min( dp[i - 1][1], dp[i - 1][0] );

			if (a[i] != b[i])
				  dp[i][1] = min( dp[i - 1][1], dp[i - 1][0] + 1);
				  
				 
			dp[i][0] = min( dp[i][0], get(0, 1, 0, i - 1) + 1 );
			dp[i][0] = min( dp[i][0], get(0, 0, 0, i - 1) + 1 );
			
			dp[i][1] = min( dp[i][1], get(1, 0, 0, i - 1) + 1 );
			dp[i][1] = min( dp[i][1], get(1, 1, 0, i - 1) + 1 );
			
			dp[i][1] = min( dp[i][1], get(0, 0, 0, i - 1) - (b[i] == '0') + 2 );
			dp[i][1] = min( dp[i][1], get(0, 1, 0, i - 1) - (b[i] == '1') + 2 );

			//dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 1 ) - (b[j] == '1') + 1 );
			//dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 0 ) - (b[j] == '0') + 1 );

			//dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 0 ) - (b[j] == '0') - (b[i] == '0') ) + 2 );
			//dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 1 ) - (b[j] == '1') - (b[i] == '1') ) + 2 );
		
			update( 0, 0, i, i, dp[i][0] );
			update( 0, 1, i, i, dp[i][0] );
			
			update( 1, 0, i, i, dp[i][1] );
			update( 1, 1, i, i, dp[i][1] );
		}
		cout << min( dp[n][0], dp[n][1] ) << endl;
}
/**
13
0101100101001
1011111000000

13
0001101001101
0101100011011

8
11011100
01101001
**/

Compilation message (stderr)

lamp.cpp:68:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

• Subtask 1: 6 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49