oj.uz

답안 #27442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
27442 2017-07-12T15:33:52 Z gs14004 Palinilap (COI16_palinilap) C++14
100 / 100
 383 ms 23844 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

const int MAXN = 200005;

struct manacher{
	int aux[2 * MAXN - 1];
	void solve(int n, char *str, int *ret){
		for(int i=0; i<n; i++){
			aux[2*i] = str[i];
			if(i != n-1) aux[2*i+1] = -1;
		}
		int p = 0, c = 0;
		for(int i=0; i<2*n-1; i++){
			int cur = 0;
			if(i <= p) cur = min(ret[2 * c - i], p - i);
			while(i - cur - 1 >= 0 && i + cur + 1 < 2*n-1 && aux[i-cur-1] == aux[i+cur+1]){
				cur++;
			}
			if(i + cur > p){
				p = i + cur;
				c = i;
			}
			ret[i] = cur;
		}
	}
}manacher;

struct sfxarray{
	int ord[MAXN], nord[MAXN], cnt[MAXN], aux[MAXN];
	void solve(int n, char *str, int *sfx, int *rev, int *lcp){
		int p = 1;
		memset(ord, 0, sizeof(ord));
		for(int i=0; i<n; i++){
			sfx[i] = i;
			ord[i] = str[i];
		}
		int pnt = 1;
		while(1){
			memset(cnt, 0, sizeof(cnt));
			for(int i=0; i<n; i++){
				cnt[ord[min(i+p, n)]]++;
			}
			for(int i=1; i<=n || i<=255; i++){
				cnt[i] += cnt[i-1];
			}
			for(int i=n-1; i>=0; i--){
				aux[--cnt[ord[min(i+p, n)]]] = i;
			}
			memset(cnt, 0, sizeof(cnt));
			for(int i=0; i<n; i++){
				cnt[ord[i]]++;
			}
			for(int i=1; i<=n || i<=255; i++){
				cnt[i] += cnt[i-1];
			}
			for(int i=n-1; i>=0; i--){
				sfx[--cnt[ord[aux[i]]]] = aux[i];
			}
			if(pnt == n) break;
			pnt = 1;
			nord[sfx[0]] = 1;
			for(int i=1; i<n; i++){
				if(ord[sfx[i-1]] != ord[sfx[i]] || ord[sfx[i-1] + p] != ord[sfx[i] + p]){
					pnt++;
				}
				nord[sfx[i]] = pnt;
			}
			memcpy(ord, nord, sizeof(int) * n);
			p *= 2;
		}
		for(int i=0; i<n; i++){
			rev[sfx[i]] = i;
		}
		int h = 0;
		for(int i=0; i<n; i++){
			if(rev[i]){
				int prv = sfx[rev[i] - 1];
				while(str[prv + h] == str[i + h]) h++;
				lcp[rev[i]] = h;
			}
			h = max(h-1, 0);
		}
	}
}sfxarray;

struct rmq{
	int tree[530000], lim;
	void init(int n, int *a){
		memset(tree, 0x3f, sizeof(tree));
		for(lim = 1; lim <= n; lim <<= 1);
		for(int i=1; i<=n; i++){
			tree[i+lim] = a[i];
		}
		for(int i=lim; i; i--){
			tree[i] = min(tree[2*i], tree[2*i+1]);
		}
	}
	int query(int s, int e){
		s += lim;
		e += lim;
		int ret = 1e9;
		while(s < e){
			if(s%2 == 1) ret = min(ret, tree[s++]);
			if(e%2 == 0) ret = min(ret, tree[e--]);
			s >>= 1;
			e >>= 1;
		}
		if(s == e) ret = min(ret, tree[s]);
		return ret;
	}
}rmq;

int n;
char str[100005], con[200005];
int dp[200005], sfx[200005], rev[200005], lcp[200005];
lint kill[100005];

struct qry{
	int p1, p2, v;
	bool operator<(const qry &q)const{
		return pi(p1, p2) < pi(q.p1, q.p2);
	}
};

vector<qry> v;

int query(int s, int e){
	if(s < 0 || e < 0 || s >= n || e >= n) return 0;
	e = 2 * n - e;
	s = rev[s], e = rev[e];
	if(s > e) swap(s, e);
	return rmq.query(s+1, e);
}

lint solve(int s, int e){
	int pos = v[s].p1;
	lint ret = -kill[pos] + 1 + dp[pos * 2] / 2;
	for(int j=s; j<=e; j++){
		if(v[j].v < 2*pos){
			ret += 1 + query(pos + 1, v[j].v - pos - 1);
		}
		else{
			ret += 1 + query(v[j].v - pos + 1, pos - 1);
		}
	}
	return ret;
}

lint dx1[100005], dx2[100005];

int main(){
	cin >> str;
	n = strlen(str);
	con[n] = '#';
	for(int i=0; i<n; i++){
		con[i] = con[2*n-i] = str[i];
	}
	manacher.solve(n, str, dp);
	sfxarray.solve(2*n+1, con, sfx, rev, lcp);
	rmq.init(2*n+1, lcp);
	lint ret = 0;
	for(int i=0; i<n; i++){
		int d = dp[2*i] / 2;
		ret += d + 1;
		dx1[i-d] += d + 1 - i;
		dx1[i+1] -= d + 1 - i;
		dx1[i+1] += d + 1 + i;
		dx1[i+d+1] -= d + 1 + i;
		dx2[i-d] += 1;
		dx2[i+1] -= 1;
		dx2[i+1] -= 1;
		dx2[i+d+1] += 1;
		/*for(int j=i-d; j<=i; j++){
			kill[j] += d + 1 - (i - j);
		}
		for(int j=i+1; j<=i+d; j++){
			kill[j] += d + 1 - (j - i);
		}*/
		if(i+d+1 < n && i-d-1 >= 0){
			v.push_back({i+d+1, str[i-d-1] - 'a', 2*i});
			v.push_back({i-d-1, str[i+d+1] - 'a', 2*i});
		}
	}
	for(int i=1; i<n; i++){
		int d = (1 + dp[2*i-1]) / 2;
		ret += d;
		dx1[i-d] += d+1-i;
		dx1[i] -= d+1-i;
		dx1[i] += d+i;
		dx1[i+d] -= d+i;
		dx2[i-d] += 1;
		dx2[i] -= 1;
		dx2[i] -= 1;
		dx2[i+d] += 1;
		/*for(int j=i-d; j<i; j++){
			kill[j] += d + 1 - (i - j);
		}
		for(int j=i; j<i+d; j++){
			kill[j] += d - (j - i);
		}*/
		if(i - d - 1 >= 0 && i + d < n){
			v.push_back({i+d, str[i-d-1] - 'a', 2*i-1});
			v.push_back({i-d-1, str[i+d] - 'a', 2*i-1});
		}
	}
	for(int i=1; i<n; i++){
		dx1[i] += dx1[i-1];
		dx2[i] += dx2[i-1];
	}
	for(int i=0; i<n; i++){
		kill[i] = dx1[i] + i * dx2[i];
	}
	sort(v.begin(), v.end());
	lint add = 0;
	for(int i=0; i<v.size(); ){
		int e = i;
		while(e < v.size() && pi(v[i].p1, v[i].p2) == pi(v[e].p1, v[e].p2)) e++;
		if(str[v[i].p1] != v[i].p2 + 'a') add = max(add, solve(i, e-1));
		i = e;
	}
	cout << ret + add;
}

Compilation message

palinilap.cpp: In function 'int main()':
palinilap.cpp:237:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); ){
                ^
palinilap.cpp:239:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(e < v.size() && pi(v[i].p1, v[i].p2) == pi(v[e].p1, v[e].p2)) e++;
           ^

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 14544 KB Output is correct
2 Correct 0 ms 14544 KB Output is correct
3 Correct 0 ms 14544 KB Output is correct
4 Correct 0 ms 14544 KB Output is correct
5 Correct 0 ms 14544 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 14912 KB Output is correct
2 Correct 3 ms 14912 KB Output is correct
3 Correct 6 ms 15204 KB Output is correct
4 Correct 3 ms 14912 KB Output is correct
5 Correct 6 ms 15204 KB Output is correct
6 Correct 13 ms 15204 KB Output is correct
7 Correct 6 ms 15204 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 326 ms 23844 KB Output is correct
2 Correct 123 ms 23844 KB Output is correct
3 Correct 123 ms 19236 KB Output is correct
4 Correct 309 ms 23844 KB Output is correct
5 Correct 296 ms 23844 KB Output is correct
6 Correct 283 ms 23844 KB Output is correct
7 Correct 346 ms 23844 KB Output is correct
8 Correct 73 ms 14544 KB Output is correct
9 Correct 356 ms 23844 KB Output is correct
10 Correct 379 ms 23844 KB Output is correct
11 Correct 153 ms 23844 KB Output is correct
12 Correct 206 ms 23844 KB Output is correct
13 Correct 169 ms 23844 KB Output is correct
14 Correct 269 ms 23844 KB Output is correct
15 Correct 263 ms 23844 KB Output is correct
16 Correct 126 ms 23844 KB Output is correct
17 Correct 219 ms 23844 KB Output is correct
18 Correct 346 ms 23844 KB Output is correct
19 Correct 383 ms 23844 KB Output is correct