| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 104997 |
2019-04-10T05:22:29 Z |
antimirage |
Lamps (JOI19_lamps) |
C++14 |
|
32 ms |
16248 KB |
# include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n, dp[N][2];
string a, b;
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)
{
if (i == -1)
t11[v].val += t11[v].must;
if (j == -1)
t10[v].val += t10[v].must;
else
t[i][j][v].val += t[i][j][v].must;
if (tl != tr){
if (i == -1)
t11[v + v].must += t11[v].must,
t11[v + v + 1].must += t11[v].must;
if (j == -1)
t10[v + v].must += t10[v].must,
t10[v + v + 1].must += t10[v].must;
else
t[i][j][v + v].must += t[i][j][v].must,
t[i][j][v + v + 1].must += t[i][j][v].must;
}
if (i == -1)
t11[v].must = 0;
else if (j == -1)
t10[v].must = 0;
else
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){
if (i == -1)
t11[v].must += val;
if (j == -1)
t10[v].must += val;
else
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);
if (i == -1)
t11[v].val = min( t11[v + v].val, t11[v + v + 1].val );
else if (j == -1)
t10[v].val = min( t10[v + v].val, t10[v + v + 1].val );
else
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){
if (i == -1)
return t11[v].val;
if (j == -1)
return t10[v].val;
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;
dp[0][0] = 0;
update( 1, 0, 0, 0, dp[0][1] );
update( 1, 1, 0, 0, dp[0][1] );
update( -1, 0, 0, 0, dp[0][1] );
update( 0, -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);
if (b[i] == '1')
update(-1, 0, 0, i - 2, +1);
if (b[i] == '0')
update(0, -1, 0, i - 2, +1);
}
if (b[i] == '1')
update(-1, 0, i - 1, i - 1, -1);
if (b[i] == '0')
update(0, -1, i - 1, i - 1, -1);
if (b[i] == '1')
update(-1, 0, i - 1, i - 1, +1);
if (b[i] == '0')
update(0, -1, i - 1, i - 1, +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], get(-1, 0, 0, i - 1) + 1 );
dp[i][0] = min( dp[i][0], get(0, -1, 0, i - 1) + 1 );
dp[i][1] = min( dp[i][1], get(0, -1, 0, i - 1) - (b[i] == '0') + 2 );
dp[i][1] = min( dp[i][1], get(-1, 0, 0, i - 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] );
update( -1, 0, i, i, dp[i][1] );
update( 0, -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
lamp.cpp:95:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main(){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
16248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
16248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
16120 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
32 ms |
16248 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
