Submission #1178768
Source Code Expand
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;
public class Main {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static int[] from = new int[4000000];
static int[] to = new int[4000000];
static int gp = 0;
static int id;
static void solve()
{
gp = 0;
int n = ni();
id = n;
int[] L = na(n);
int[] R = na(n);
dfs(0, n, L, R);
int[][] g = packD(id, from, to, gp);
int[] clus = decomposeToSCC(g);
int[][] cg = condense(g, clus);
int m = cg.length;
int[] score = new int[m];
for(int i = 0;i < n;i++){
score[clus[i]]++;
}
int[] dp = new int[m];
for(int i = m-1;i >= 0;i--){
dp[i] += score[i];
for(int e : cg[i]){
dp[e] = Math.max(dp[e], dp[i]);
}
}
out.println(Arrays.stream(dp).max().getAsInt());
}
static void dfs(int l, int r, int[] B, int[] A)
{
int h = (l+r)/2;
int[][] poss = new int[2*(r-l)][];
int p = 0;
for(int i = l;i < r;i++){
poss[p++] = new int[]{A[i]-Math.abs(i-h), i, 0};
poss[p++] = new int[]{B[i]+Math.abs(i-h), i, 1};
}
Arrays.sort(poss, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
if(a[0] != b[0])return Integer.compare(a[0], b[0]);
return -(a[2] - b[2]);
}
});
int bid = id;
id++;
for(int i = p-2;i >= 0;i--){
from[gp] = id-1;
to[gp] = id;
gp++;
id++;
}
for(int i = p-1;i >= 0;i--){
if(poss[i][2] == 0){
from[gp] = poss[i][1];
to[gp] = bid + (p-1-i);
gp++;
}else{
from[gp] = bid + (p-1-i);
to[gp] = poss[i][1];
gp++;
}
}
if(r-l > 1){
dfs(l, h, B, A);
dfs(h, r, B, A);
}
}
public static int[][] packD(int n, int[] from, int[] to){ return packD(n, from, to, from.length);}
public static int[][] packD(int n, int[] from, int[] to, int sup)
{
int[][] g = new int[n][];
int[] p = new int[n];
for(int i = 0;i < sup;i++)p[from[i]]++;
for(int i = 0;i < n;i++)g[i] = new int[p[i]];
for(int i = 0;i < sup;i++){
g[from[i]][--p[from[i]]] = to[i];
}
return g;
}
public static int[] decomposeToSCC(int[][] g)
{
int n = g.length;
int[] stack = new int[n+1];
int[] ind = new int[n+1];
int[] ord = new int[n];
Arrays.fill(ord, -1);
int[] low = new int[n];
Arrays.fill(low, -1);
int sp = 0;
int id = 0; // preorder
int[] clus = new int[n];
int cid = 0;
int[] cstack = new int[n+1];
int csp = 0;
boolean[] incstack = new boolean[n];
for(int i = 0;i < n;i++){
if(ord[i] == -1){
ind[sp] = 0;
cstack[csp++] = i;
stack[sp++] = i;
incstack[i] = true;
while(sp > 0){
int cur = stack[sp-1];
if(ind[sp-1] == 0){
ord[cur] = low[cur] = id++;
}
if(ind[sp-1] < g[cur].length){
int nex = g[cur][ind[sp-1]];
if(ord[nex] == -1){
ind[sp-1]++;
ind[sp] = 0;
incstack[nex] = true;
cstack[csp++] = nex;
stack[sp++] = nex;
}else{
// shortcut
// U.tr(cur, nex, incstack[nex], low[nex], stack);
if(incstack[nex])low[cur] = Math.min(low[cur], low[nex]);
ind[sp-1]++;
}
}else{
if(ord[cur] == low[cur]){
while(csp > 0){
incstack[cstack[csp-1]] = false;
clus[cstack[--csp]] = cid;
if(cstack[csp] == cur)break;
}
cid++;
}
if(--sp >= 1)low[stack[sp-1]] = Math.min(low[stack[sp-1]], low[stack[sp]]);
}
}
}
}
return clus;
}
public static int[][] condense(int[][] g, int[] clus)
{
int n = g.length;
int m = 0;
for(int i = 0;i < n;i++)m = Math.max(m, clus[i]);
m++;
int[] cp = new int[m];
for(int i = 0;i < n;i++){
cp[clus[i]] += g[i].length;
}
int[][] c = new int[m][];
for(int i = 0;i < m;i++){
c[i] = new int[cp[i]];
}
for(int i = 0;i < n;i++){
for(int j = 0;j < g[i].length;j++){
c[clus[i]][--cp[clus[i]]] = clus[g[i][j]];
}
}
for(int i = 0;i < m;i++){
Arrays.sort(c[i]);
int jp = 0;
for(int j = 0;j < c[i].length;j++){
if((j == 0 || c[i][j] != c[i][j-1]) && c[i][j] != i){
c[i][jp++] = c[i][j];
}
}
c[i] = Arrays.copyOf(c[i], jp);
}
return c;
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
// private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private static char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private static char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Submission Info
Submission Time |
|
Task |
E - 遊園地 |
User |
uwi |
Language |
Java8 (OpenJDK 1.8.0) |
Score |
1200 |
Code Size |
7560 Byte |
Status |
AC |
Exec Time |
2757 ms |
Memory |
282948 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
1200 / 1200 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
All |
in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, in28.txt, in29.txt, in3.txt, in30.txt, in31.txt, in32.txt, in33.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt |
Case Name |
Status |
Exec Time |
Memory |
in1.txt |
AC |
2143 ms |
235892 KB |
in10.txt |
AC |
2324 ms |
245780 KB |
in11.txt |
AC |
2088 ms |
226336 KB |
in12.txt |
AC |
2160 ms |
243472 KB |
in13.txt |
AC |
2118 ms |
257160 KB |
in14.txt |
AC |
2073 ms |
251708 KB |
in15.txt |
AC |
1967 ms |
222628 KB |
in16.txt |
AC |
2070 ms |
225268 KB |
in17.txt |
AC |
2334 ms |
256328 KB |
in18.txt |
AC |
2088 ms |
227632 KB |
in19.txt |
AC |
2165 ms |
221368 KB |
in2.txt |
AC |
2757 ms |
253528 KB |
in20.txt |
AC |
2083 ms |
226744 KB |
in21.txt |
AC |
2266 ms |
279628 KB |
in22.txt |
AC |
2147 ms |
278824 KB |
in23.txt |
AC |
2059 ms |
280640 KB |
in24.txt |
AC |
2311 ms |
265672 KB |
in25.txt |
AC |
2132 ms |
282948 KB |
in26.txt |
AC |
154 ms |
58324 KB |
in27.txt |
AC |
155 ms |
57928 KB |
in28.txt |
AC |
169 ms |
56532 KB |
in29.txt |
AC |
2078 ms |
225092 KB |
in3.txt |
AC |
2430 ms |
266048 KB |
in30.txt |
AC |
1926 ms |
224376 KB |
in31.txt |
AC |
2135 ms |
228904 KB |
in32.txt |
AC |
2101 ms |
227300 KB |
in33.txt |
AC |
2178 ms |
232508 KB |
in4.txt |
AC |
2212 ms |
251152 KB |
in5.txt |
AC |
1823 ms |
232388 KB |
in6.txt |
AC |
2090 ms |
236900 KB |
in7.txt |
AC |
2340 ms |
249172 KB |
in8.txt |
AC |
2266 ms |
251356 KB |
in9.txt |
AC |
2156 ms |
249028 KB |
sample1.txt |
AC |
163 ms |
57044 KB |
sample2.txt |
AC |
162 ms |
57940 KB |
sample3.txt |
AC |
151 ms |
57300 KB |