結果
| 問題 | No.1036 Make One With GCD 2 |
| ユーザー |
 k_6101
|
| 提出日時 | 2020-04-26 18:32:57 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 754 ms / 2,000 ms |
| コード長 | 6,375 bytes |
| コンパイル時間 | 3,056 ms |
| コンパイル使用メモリ | 82,600 KB |
| 実行使用メモリ | 86,756 KB |
| 最終ジャッジ日時 | 2024-09-16 14:14:40 |
| 合計ジャッジ時間 | 22,405 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 41 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.net.ConnectException;import java.rmi.dgc.Lease;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Arrays;import java.util.Collections;import java.util.Deque;import java.util.HashMap;import java.util.HashSet;import java.util.List;import java.util.Map;import java.util.NoSuchElementException;import java.util.Objects;import java.util.Set;import java.util.Stack;import java.util.TreeMap;import java.util.TreeSet;import static java.util.Comparator.*;public class Main {public static void main(String[] args) {Main main = new Main();main.solve();main.out.close();}// ======================================================================// yukicoder 1036 Make One With GCD 2//public void solve() {int N = ni();long[] A = nl(N);SWAG swag = new SWAG(f);long ans = 0;int right = 0;boolean f;for (int left = 0; left < N; left++) { // 左から順番にf = false;while(right < N && swag.fold_all() != 1) { // 尺取りswag.push(A[right]);right++;}if(swag.fold_all() == 1) ans += (N - right + 1);swag.pop();}out.println(ans);}// SWAG 計算用関数のサンプルF f = new F() {@Overridepublic long calc(long p1, long p2) {return gcd(p1, p2);}};public interface F {long calc(long p1, long p2);}// Sliding Window Aggregationclass SWAG {private Deque<PPL> front = new ArrayDeque<PPL>(); // 前スタックprivate Deque<PPL> back = new ArrayDeque<PPL>(); // 後ろスタックprivate F f;public SWAG(F f) { this.f = f; }// 空チェックboolean isEmpty() { return front.isEmpty() && back.isEmpty(); }// データ数を返すint size() { return front.size() + back.size(); }// 現在の全体の計算値を返すlong fold_all() {if(isEmpty()) return 0;else if(front.isEmpty()) {return back.peekLast().val;} else if(back.isEmpty()) {return front.peekLast().val;} else {return f.calc(front.peekLast().val, back.peekLast().val);}}// キューの最後に値を追加するvoid push(long key) {if(back.isEmpty()) { // 空なら、計算値には値をそのまま設定するback.offerLast(new PPL(key, key));} else { // 一つ前の計算結果と値で、新しい計算結果を設定するback.offerLast(new PPL(key, f.calc(key, back.peekLast().val)));}}// キューの先頭から値を取り出して、削除するlong pop() {if(isEmpty()) return 0;else if(front.isEmpty()) {PPL pp = back.pollLast();front.offerLast(new PPL(pp.key, pp.key)); // back の一番後ろを front へ移動while(!back.isEmpty()) { // back の残りを再計算しながら front へpp = back.pollLast();front.offerLast(new PPL(pp.key, f.calc(pp.key, front.peekLast().val)));}}return front.pollLast().key;}}class PPL {public long key, val;public PPL(long key, long val) {this.key = key;this.val = val;}public long getKey() { return key; }public void setKey(long key) { this.key = key; }public long getVal() { return val; }public void setVal(long val) { this.val = val; }}// 最大公約数の取得long gcd(long a, long b) {if (b == 0)return a;return gcd(b, a % b);}// ------------------------------------------// ライブラリ// ------------------------------------------private PrintWriter out = new PrintWriter(System.out);// Scannerprivate FastScanner scan = new FastScanner();int ni() {return scan.nextInt();}int[] ni(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) {a[i] = ni();}return a;}int[][] ni(int y, int x) {int[][] a = new int[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = ni();}}return a;}long nl() {return scan.nextLong();}long[] nl(int n) {long[] a = new long[n];for (int i = 0; i < n; i++) {a[i] = nl();}return a;}long[][] nl(int y, int x) {long[][] a = new long[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = nl();}}return a;}String ns() {return scan.next();}String[] ns(int n) {String[] a = new String[n];for (int i = 0; i < n; i++) {a[i] = ns();}return a;}String[][] ns(int y, int x) {String[][] a = new String[y][x];for (int i = 0; i < y; i++) {for (int j = 0; j < x; j++) {a[i][j] = ns();}}return a;}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte())return buffer[ptr++];elsereturn -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}public boolean hasNext() {while (hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext())throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}public int nextInt() {long nl = nextLong();if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE)throw new NumberFormatException();return (int) nl;}public double nextDouble() {return Double.parseDouble(next());}}