Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

[JAVA] 1110MS

Posted by freesomewhere at 2022-06-02 15:00:44 on Problem 3368
import java.io.*;
import java.util.*;

public class Main {
public static class Scanner {
    BufferedReader br;
    StringTokenizer st;

    public Scanner(InputStream s) {
        br = new BufferedReader(new InputStreamReader(s));
    }

    public Scanner(FileReader f) {
        br = new BufferedReader(f);
    }

    public String next() throws IOException {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public int[] nextIntArr(int n) throws IOException {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(next());
        }
        return arr;
    }
}

    public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int N = 100001;

    static int[] log2 = new int[N];

    static void make() {
        int cnt = -1;
        log2[0] = -1;
        for (int i = 1; i < N; i++) {
            cnt += ((i & (i - 1)) == 0) ? 1 : 0;
            log2[i] = cnt;
        }
    }

    int[][] st;
    int n;

    public Main() {
    }

    public void init(int n, int[] a) {
        this.n = n;
        int k = log2[n];
        st = new int[n][k + 1];
        for (int i = 0; i < n; i++) {
            st[i][0] = a[i];
        }
        for (int j = 1; j <= k; j++) {
            for (int i = 0; i < n; i++) {
                int i2 = i + (1 << (j - 1));
                if (i2 >= n) break;
                st[i][j] = Math.max(st[i][j - 1], st[i2][j - 1]);
            }
        }
    }

    public int query(int l, int r) {
        if (l > r) return 0;
        int k = log2[r - l + 1];
        return Math.max(st[l][k], st[r - (1 << k) + 1][k]);
    }

    public static void main(String[] args) throws IOException {
        Scanner scanner = new Scanner(System.in);
        make();
        int n = scanner.nextInt();
        while (n != 0) {
            int q = scanner.nextInt();
            int[] a = new int[n];
            int[] fs = new int[n];
            Arrays.fill(fs, 1);
            for (int i = 0; i < n; i++) {
                a[i] = scanner.nextInt();
            }
            for (int i = 1; i < n; i++) {
                if (a[i] == a[i - 1]) {
                    fs[i] = fs[i - 1] + 1;
                }
            }
            Main main = new Main();
            main.init(n, fs);
            for (int i = 0; i < q; i++) {
                int l = scanner.nextInt() - 1;
                int r = scanner.nextInt() - 1;
                if (l == 0) {
                    out.println(main.query(l, r));
                } else {
                    int t = l;
                    while (t <= r && a[t - 1] == a[t]) {
                        t++;
                    }
                    int x = t - l;
                    out.println(Math.max(x, main.query(t, r)));
                }
            }
            n = scanner.nextInt();
        }
        out.flush();
        out.close();
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator