結果

問題 No.1031 いたずら好きなお姉ちゃん
ユーザー uwi
提出日時 2020-04-17 22:28:29
言語 Java
(openjdk 23)
結果
AC  
実行時間 356 ms / 3,500 ms
コード長 8,185 bytes
コンパイル時間 4,119 ms
コンパイル使用メモリ 86,212 KB
実行使用メモリ 81,696 KB
最終ジャッジ日時 2024-10-03 14:02:11
合計ジャッジ時間 19,608 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 53
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package contest200417;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E {
    InputStream is;
    PrintWriter out;
    String INPUT = "";
    
    void solve()
    {
        int n = ni();
        int[] a = na(n);
        
        out.println(go(a) + go(rev(a)));
    }
    
    public static int[] rev(int[] a){int[] b = new int[a.length];for(int i = 0;i < a.length;i++)b[a.length-1-i] = a[i];return b;}
    
    long go(int[] a)
    {       
        int n = a.length;
        int[] pw = enumPrevWall(a);
        int[] par = new int[n+1];
        for(int i = 0;i < n;i++){
            if(pw[i] == -1){
                par[i] = n;
            }else{
                par[i] = pw[i];
            }
        }
        par[n] = -1;
        int[][] g = parentToG(par);
        
        int[][] spar = logstepParents(par);
        int[][] pars = parents3(g, n);
        int[] dep = pars[2];
        
        SegmentTreeRMQ st = new SegmentTreeRMQ(a);
        long ans = 0;
        for(int i = 0;i < n;i++){
            int last = st.lastle(i-1, a[i]);
            if(last != -1){
                int lca = lca2(last, i, spar, dep);
                ans -= dep[lca];
            }
            
            ans += dep[i];
        }
        return ans-n;
    }
    
    public static class SegmentTreeRMQ {
        public int M, H, N;
        public int[] st;
        
        public SegmentTreeRMQ(int n)
        {
            N = n;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            st = new int[M];
            Arrays.fill(st, 0, M, Integer.MAX_VALUE);
        }
        
        public SegmentTreeRMQ(int[] a)
        {
            N = a.length;
            M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
            H = M>>>1;
            st = new int[M];
            for(int i = 0;i < N;i++){
                st[H+i] = a[i];
            }
            Arrays.fill(st, H+N, M, Integer.MAX_VALUE);
            for(int i = H-1;i >= 1;i--)propagate(i);
        }
        
        public void update(int pos, int x)
        {
            st[H+pos] = x;
            for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
        }
        
        private void propagate(int i)
        {
            st[i] = Math.min(st[2*i], st[2*i+1]);
        }
        
        public int minx(int l, int r){
            int min = Integer.MAX_VALUE;
            if(l >= r)return min;
            while(l != 0){
                int f = l&-l;
                if(l+f > r)break;
                int v = st[(H+l)/f];
                if(v < min)min = v;
                l += f;
            }
            
            while(l < r){
                int f = r&-r;
                int v = st[(H+r)/f-1];
                if(v < min)min = v;
                r -= f;
            }
            return min;
        }
        
        public int min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
        
        private int min(int l, int r, int cl, int cr, int cur)
        {
            if(l <= cl && cr <= r){
                return st[cur];
            }else{
                int mid = cl+cr>>>1;
                int ret = Integer.MAX_VALUE;
                if(cl < r && l < mid){
                    ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
                }
                if(mid < r && l < cr){
                    ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
                }
                return ret;
            }
        }
        
        public int firstle(int l, int v) {
            if(l >= H)return -1;
            int cur = H+l;
            while(true){
                if(st[cur] <= v){
                    if(cur >= H)return cur-H;
                    cur = 2*cur;
                }else{
                    cur++;
                    if((cur&cur-1) == 0)return -1;
                    if((cur&1)==0)cur>>>=1;
                }
            }
        }
        
        public int lastle(int l, int v) {
            if(l < 0)return -1;
            int cur = H+l;
            while(true){
                if(st[cur] <= v){
                    if(cur >= H)return cur-H;
                    cur = 2*cur + 1;
                }else{
                    if((cur&cur-1) == 0)return -1;
                    cur--;
                    if((cur&1)==1)cur>>>=1;
                }
            }
        }
    }
    
    public static int lca2(int a, int b, int[][] spar, int[] depth) {
        if (depth[a] < depth[b]) {
            b = ancestor(b, depth[b] - depth[a], spar);
        } else if (depth[a] > depth[b]) {
            a = ancestor(a, depth[a] - depth[b], spar);
        }
        if (a == b)
            return a;
        int sa = a, sb = b;
        for (int low = 0, high = depth[a], t = Integer.highestOneBit(high), k = Integer
                .numberOfTrailingZeros(t); t > 0; t >>>= 1, k--) {
            if ((low ^ high) >= t) {
                if (spar[k][sa] != spar[k][sb]) {
                    low |= t;
                    sa = spar[k][sa];
                    sb = spar[k][sb];
                } else {
                    high = low | t - 1;
                }
            }
        }
        return spar[0][sa];
    }
    protected static int ancestor(int a, int m, int[][] spar) {
        for (int i = 0; m > 0 && a != -1; m >>>= 1, i++) {
            if ((m & 1) == 1)
                a = spar[i][a];
        }
        return a;
    }
    public static int[][] logstepParents(int[] par) {
        int n = par.length;
        int m = Integer.numberOfTrailingZeros(Integer.highestOneBit(n - 1)) + 1;
        int[][] pars = new int[m][n];
        pars[0] = par;
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                pars[j][i] = pars[j - 1][i] == -1 ? -1 : pars[j - 1][pars[j - 1][i]];
            }
        }
        return pars;
    }
    
    public static int[][] parents3(int[][] g, int root) {
        int n = g.length;
        int[] par = new int[n];
        Arrays.fill(par, -1);
        int[] depth = new int[n];
        depth[0] = 0;
        int[] q = new int[n];
        q[0] = root;
        for (int p = 0, r = 1; p < r; p++) {
            int cur = q[p];
            for (int nex : g[cur]) {
                if (par[cur] != nex) {
                    q[r++] = nex;
                    par[nex] = cur;
                    depth[nex] = depth[cur] + 1;
                }
            }
        }
        return new int[][] { par, q, depth };
    }
    
    public static int[][] parentToG(int[] par)
    {
        int n = par.length;
        int[] ct = new int[n];
        for(int i = 0;i < n;i++){
            if(par[i] >= 0){
                ct[i]++;
                ct[par[i]]++;
            }
        }
        int[][] g = new int[n][];
        for(int i = 0;i < n;i++){
            g[i] = new int[ct[i]];
        }
        for(int i = 0;i < n;i++){
            if(par[i] >= 0){
                g[par[i]][--ct[par[i]]] = i;
                g[i][--ct[i]] = par[i];
            }
        }
        return g;
    }
    
    
    
    
    public static int[] enumPrevWall(int[] a)
    {
        int n = a.length;
        int[] L = new int[n];
        L[0] = -1;
        for(int i = 1;i < n;i++){
            L[i] = i-1;
            while(L[i] >= 0 && a[L[i]] < a[i])L[i] = L[L[i]];
        }
        return L;
    }
    
    void run() throws Exception
    {
        is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        solve();
        out.flush();
        if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//      Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){
//          @Override
//          public void run() {
//              long s = System.currentTimeMillis();
//              solve();
//              out.flush();
//              if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
//          }
//      };
//      t.start();
//      t.join();
    }
    
    public static void main(String[] args) throws Exception { new E().run(); }
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private 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 boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private 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 int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private long[] nal(int n)
    {
        long[] a = new long[n];
        for(int i = 0;i < n;i++)a[i] = nl();
        return a;
    }
    
    private 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 int[][] nmi(int n, int m) {
        int[][] map = new int[n][];
        for(int i = 0;i < n;i++)map[i] = na(m);
        return map;
    }
    
    private int ni() { return (int)nl(); }
    
    private 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) { System.out.println(Arrays.deepToString(o)); }
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0