oj.uz

Submission #221855

# Submission time Handle Problem Language Result Execution time Memory
221855 2020-04-11T10:08:16 Z _7_7_ Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 31200 KB 
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e6 + 11;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;


int n, dp[N][2], prv[N], T[N << 2][2];
char s[N], t[N];

void update (int pos, int lvl, int x, int v = 1, int tl = 0, int tr = n) {
	if (tl == tr) {
		T[v][lvl] = x;
		return;
	}

	int tm = (tl + tr) >> 1;
	if (pos <= tm)
		update(pos, lvl, x, v << 1, tl, tm);
	else	
		update(pos, lvl, x, v << 1 | 1, tm + 1, tr);
	T[v][lvl] = min(T[v << 1][lvl], T[v << 1 | 1][lvl]);
}

int get (int l, int r, int lvl, int v = 1, int tl = 0, int tr = n) {
	if (l > r || tl > r || l > tr)
		return inf;

	if (l <= tl && tr <= r)
		return T[v][lvl];

	int tm = (tl + tr) >> 1;
	return min(get(l, r, lvl, v << 1, tl, tm), get(l, r, lvl, v << 1 | 1, tm + 1, tr));
}

main () {
	scanf("%d\n%s\n%s", &n, s + 1, t + 1);
	for (int i = 1; i <= n; ++i) {
		prv[i] = i - 1;
		if (i > 1 && t[i] == t[i - 1])
			prv[i] = prv[i - 1];
	}	
		

	dp[0][1] = inf;
	update(0, 1, inf);

	int lst = 0;
	for (int i = 1; i <= n; ++i) {
		if (s[i] == t[i]) {
			dp[i][0] = min(dp[i - 1][0], min(get(prv[i], i - 1, 0) + 1, get(prv[i], i - 1, 1)));
			dp[i][1] = inf;
			lst = i;
		} else {
			dp[i][0] = min(get(prv[i], i - 1, 0), get(prv[i], i - 1, 1)) + 1;
			dp[i][1] = min(get(lst, i - 1, 0), get(lst, i - 1, 1)) + 1;
		} 

//		cerr << dp[i][0] << ' ' << dp[i][1] << endl;

		update(i, 0, dp[i][0]);
		update(i, 1, dp[i][1]);
	}


	cout << min(dp[n][0], dp[n][1]) << endl;		
}

Compilation message

lamp.cpp:69:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
lamp.cpp: In function 'int main()':
lamp.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n%s\n%s", &n, s + 1, t + 1);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 650 ms 31096 KB Output is correct
8 Correct 810 ms 31200 KB Output is correct
9 Correct 858 ms 30968 KB Output is correct
10 Correct 857 ms 30968 KB Output is correct
11 Correct 841 ms 31164 KB Output is correct
12 Correct 853 ms 30968 KB Output is correct
13 Execution timed out 1034 ms 30860 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 4 ms 384 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Incorrect 5 ms 384 KB Output isn't correct
17 Halted 0 ms 0 KB -