結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 37zigen
|
| 提出日時 | 2017-12-14 23:56:38 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 12,509 bytes |
| コンパイル時間 | 3,222 ms |
| コンパイル使用メモリ | 89,100 KB |
| 実行使用メモリ | 72,788 KB |
| 最終ジャッジ日時 | 2024-12-22 21:22:36 |
| 合計ジャッジ時間 | 19,293 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | WA * 1 |
| other | WA * 35 |
ソースコード
//制約の確認import java.io.IOException;import java.io.InputStream;import java.util.Arrays;import java.util.NoSuchElementException;class Main {public static void main(String[] args) {new Main().run();}final long MOD = 1_000_000_000 + 7;int n;int[] v;String[] op;AVLTree next;SegTree_add seg_add;SegTree_mul seg_mul;void run() {Scanner sc = new Scanner();n = sc.nextInt();if (!(3 <= n && n <= 1e5 - 1) || !(n % 2 == 1)) {throw new AssertionError();}n = (n + 1) / 2;v = new int[n];op = new String[n - 1];seg_add = new SegTree_add(n);seg_mul = new SegTree_mul(n);for (int i = 0; i < n; ++i) {v[i] = sc.nextInt();if (!(0 <= v[i] && v[i] <= 9))throw new AssertionError();if (i != n - 1) {op[i] = sc.next();if (!(op[i].equals("*") || op[i].equals("+")))throw new AssertionError();}}for (int i = 0; i < n; ++i) {seg_mul.setVal(i, v[i]);}next = new AVLTree();next.insert(-1);next.insert(n - 1);for (int i = 0; i < n - 1; ++i) {if (op[i].equals("+")) {next.insert(i);}}{long tmp = 1;for (int i = 0; i < n; ++i) {if (i == 0 || op[i - 1].equals("+")) {tmp = v[i];}if (i > 0 && op[i - 1].equals("*")) {tmp = tmp * v[i] % MOD;}if (i == n - 1 || op[i].equals("+")) {seg_add.setVal(i, tmp);tmp = 1;}}}StringBuilder sb = new StringBuilder();int Q = sc.nextInt();if (!(1 <= Q && Q <= 1e5))throw new AssertionError();for (int i = 0; i < Q; ++i) {String T = sc.next();int x = sc.nextInt();int y = sc.nextInt();if (!(1 <= x && x < y && y <= 2 * n - 1 && x % 2 == y % 2 && (T.equals("?") || T.equals("!"))&& (i != Q - 1 || T.equals("?"))))throw new AssertionError();if (T.equals("?")) {x = (x - 1) / 2;y = (y - 1) / 2;long base = seg_add.query(x, y + 1);if (y < op.length && op[y].equals("*")) {int left = (int) next.ceiling(y).key;left = Math.max(left, x - 1);base = (base + prd(left, y)) % MOD;}if (x > 0 && op[x - 1].equals("*")) {int right = (int) next.floor(x - 1).key;int left = (int) next.ceiling(x - 1).key;if (right <= y) {base = base - prd(left, right) + prd(x - 1, right);while (base < 0)base += MOD;while (base >= MOD)base -= MOD;}}sb.append(base);sb.append("\n");} else {if (x % 2 == 0) {// 演算子のswapx = x / 2 - 1;y = y / 2 - 1;if (op[x].equals(op[y]))continue;if (op[x].equals("*")) {x ^= y;y ^= x;x ^= y;}{// +->*next.delete(x);seg_add.setVal(x, 0);int right = (int) next.floor(x).key;int left = (int) next.ceiling(x).key;seg_add.setVal(right, prd(left, right) % MOD);}{// * -> +int right = (int) next.floor(y).key;int left = (int) next.ceiling(y).key;seg_add.setVal(y, prd(left, y));seg_add.setVal(right, prd(y, right));next.insert(y);}{String tmp = op[x];op[x] = op[y];op[y] = tmp;}} else {// 数のswapx = (x - 1) / 2;y = (y - 1) / 2;if (v[x] == v[y])continue;if (v[x] > v[y]) {x ^= y;y ^= x;x ^= y;}seg_mul.setVal(x, v[y]);seg_mul.setVal(y, v[x]);int rightx = (int) next.floor(x).key;int leftx = (int) next.ceiling(x - 1).key;int righty = (int) next.floor(y).key;int lefty = (int) next.ceiling(y - 1).key;if (rightx != righty) {seg_add.setVal(rightx, prd(leftx, rightx));seg_add.setVal(righty, prd(lefty, righty));}v[x] ^= v[y];v[y] ^= v[x];v[x] ^= v[y];}}}System.out.println(sb);}long prd(int a, int b) {return seg_mul.query(a + 1, b + 1);}class SegTree_add {int n;long[] sum;public SegTree_add(int n_) {n = 1;while (n < n_) {n *= 2;}sum = new long[2 * n - 1];}void setVal(int k, long add) {k += n - 1;sum[k] = add;while (k > 0) {k = (k - 1) / 2;sum[k] = (sum[2 * k + 1] + sum[2 * k + 2]) % MOD;}}long query(int a, int b) {return query(a, b, 0, n, 0);}long query(int a, int b, int l, int r, int k) {if (b <= l || r <= a) {return 0;} else if (a <= l && r <= b) {return sum[k];} else {long vl = query(a, b, l, (l + r) / 2, 2 * k + 1);long vr = query(a, b, (l + r) / 2, r, 2 * k + 2);return (vl + vr) % MOD;}}}class SegTree_mul {int n;long[] sum;public SegTree_mul(int n_) {n = 1;while (n < n_) {n *= 2;}sum = new long[2 * n - 1];Arrays.fill(sum, 1);}void setVal(int k, long add) {k += n - 1;sum[k] = add;while (k > 0) {k = (k - 1) / 2;sum[k] = (sum[2 * k + 1] * sum[2 * k + 2]) % MOD;}}long query(int a, int b) {return query(a, b, 0, n, 0);}long query(int a, int b, int l, int r, int k) {if (b <= l || r <= a) {return 1;} else if (a <= l && r <= b) {return sum[k];} else {long vl = query(a, b, l, (l + r) / 2, 2 * k + 1);long vr = query(a, b, (l + r) / 2, r, 2 * k + 2);return (vl * vr) % MOD;}}}long inv(long a) {return pow(a, MOD - 2);}long pow(long a, long n) {long ret = 1;for (; n > 0; n >>= 1, a = a * a % MOD) {if (n % 2 == 1) {ret = ret * a % MOD;}}return ret;}public static class AVLTree {Node root = null;Node ceiling(long v) {Node node = root;while (node != null) {if (min(node.right) <= v) {node = node.right;} else if (node.key <= v)return node;elsenode = node.left;}return node;}Node floor(long v) {Node node = root;while (node != null) {if (max(node.left) >= v) {node = node.left;} else if (node.key >= v)return node;elsenode = node.right;}return node;}class Node {long key;long max;long min;int height;int balance;int sz = 1;Node left = null;Node right = null;Node parent = null;public Node(long key_, Node parent_) {key = key_;parent = parent_;max = key_;min = key_;}}Node kth(long a) {Node node = root;int sum = 0;while (node != null) {if (sum + node.sz < a) {return null;}if (sum + sz(node.left) + 1 == a) {return node;}if (sum + sz(node.left) + 1 < a) {sum = sum + 1 + sz(node.left);node = node.right;} else {node = node.left;}}return null;}boolean contain(int delKey) {if (root == null)return false;Node node = root;while (node != null) {if (delKey == node.key) {return true;}node = delKey >= node.key ? node.right : node.left;}return false;}boolean delete(long key) {if (root == null)return false;Node node = root;while (node != null) {if (key == node.key) {delete(node);return true;}node = key >= node.key ? node.right : node.left;}return false;}void delete(Node node) {if (node.left == null && node.right == null) {if (node.parent == null) {root = null;return;}Node parent = node.parent;if (parent.left == node)parent.left = null;elseparent.right = null;rebalance(parent);}if (node.left != null) {Node child = node.left;while (child.right != null) {child = child.right;}node.key = child.key;delete(child);} else if (node.right != null) {Node child = node.right;while (child.left != null) {child = child.left;}node.key = child.key;delete(child);}}boolean insert(long key) {if (root == null) {root = new Node(key, null);return true;}Node cur = root;Node parent = null;while (true) {if (cur.key == key) {return false;}parent = cur;boolean goLeft = key < cur.key;cur = goLeft ? cur.left : cur.right;if (cur == null) {if (goLeft) {parent.left = new Node(key, parent);} else {parent.right = new Node(key, parent);}rebalance(parent);break;}}return true;}void rebalance(Node n) {setBalance(n);if (n.balance == -2) {if (height(n.left.left) >= height(n.left.right)) {n = rotateRight(n);} else {n = rotateLeftThenRight(n);}} else if (n.balance == 2) {if (height(n.right.right) >= height(n.right.left)) {n = rotateLeft(n);} else {n = rotateRightThenLeft(n);}}if (n.parent != null) {rebalance(n.parent);} else {root = n;}}void setBalance(Node... nodes) {for (Node n : nodes) {n.height = 1 + Math.max(height(n.right), height(n.left));n.balance = height(n.right) - height(n.left);n.sz = 1 + sz(n.left) + sz(n.right);n.max = Math.max(n != null ? n.key : -Integer.MAX_VALUE, Math.max(max(n.left), max(n.right)));n.min = Math.min(n != null ? n.key : Integer.MAX_VALUE, Math.min(min(n.left), min(n.right)));}}int sz(Node node) {return node != null ? node.sz : 0;}int height(Node node) {return node != null ? node.height : -1;}long max(Node node) {return node != null ? node.max : -Long.MAX_VALUE;}long min(Node node) {return node != null ? node.min : Long.MAX_VALUE;}Node rotateRight(Node a) {Node b = a.left;if (a.parent != null) {if (a.parent.left == a) {a.parent.left = b;} else {a.parent.right = b;}}b.parent = a.parent;a.parent = b;a.left = b.right;b.right = a;if (a.left != null)a.left.parent = a;setBalance(a, b);return b;}Node rotateLeft(Node a) {Node b = a.right;if (a.parent != null) {if (a.parent.right == a) {a.parent.right = b;} else {a.parent.left = b;}}b.parent = a.parent;a.parent = b;a.right = b.left;b.left = a;if (a.right != null)a.right.parent = a;setBalance(a, b);return b;}Node rotateLeftThenRight(Node n) {n.left = rotateLeft(n.left);return rotateRight(n);}Node rotateRightThenLeft(Node n) {n.right = rotateRight(n.right);return rotateLeft(n);}void inOrder(Node cur) {if (cur == null)return;inOrder(cur.left);System.out.println(cur.key);inOrder(cur.right);}}static void tr(Object... objects) {System.out.println(Arrays.deepToString(objects));}class Scanner {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 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());}}}