結果
| 問題 | No.619 CardShuffle |
| ユーザー |
 37zigen
|
| 提出日時 | 2017-12-14 23:56:38 |
| 言語 | Java21 (openjdk 21) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 12,509 bytes |
| コンパイル時間 | 2,553 ms |
| コンパイル使用メモリ | 78,740 KB |
| 実行使用メモリ | 82,572 KB |
| 最終ジャッジ日時 | 2023-08-24 14:00:36 |
| 合計ジャッジ時間 | 18,126 ms |
|
ジャッジサーバーID （参考情報） |
judge11 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | WA | - |
| testcase_01 | WA | - |
| testcase_02 | WA | - |
| testcase_03 | WA | - |
| testcase_04 | WA | - |
| testcase_05 | WA | - |
| testcase_06 | WA | - |
| testcase_07 | WA | - |
| testcase_08 | WA | - |
| testcase_09 | WA | - |
| testcase_10 | WA | - |
| testcase_11 | WA | - |
| testcase_12 | WA | - |
| testcase_13 | WA | - |
| testcase_14 | WA | - |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | WA | - |
| testcase_18 | WA | - |
| testcase_19 | WA | - |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
| testcase_22 | WA | - |
| testcase_23 | WA | - |
| testcase_24 | WA | - |
| testcase_25 | WA | - |
| testcase_26 | WA | - |
| testcase_27 | WA | - |
| testcase_28 | WA | - |
| testcase_29 | WA | - |
| testcase_30 | WA | - |
| testcase_31 | WA | - |
| testcase_32 | WA | - |
| testcase_33 | WA | - |
| testcase_34 | WA | - |
| testcase_35 | WA | - |
ソースコード
//制約の確認
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) {// 演算子のswap
x = 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 {// 数のswap
x = (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;
else
node = 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;
else
node = 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;
else
parent.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++];
else
return -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());
}
}
}