結果
| 問題 |
No.1000 Point Add and Array Add
|
| コンテスト | |
| ユーザー |
 tk55513
|
| 提出日時 | 2020-03-03 01:57:06 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 577 ms / 2,000 ms |
| コード長 | 24,457 bytes |
| コンパイル時間 | 3,169 ms |
| コンパイル使用メモリ | 91,308 KB |
| 実行使用メモリ | 75,048 KB |
| 最終ジャッジ日時 | 2024-10-13 21:28:36 |
| 合計ジャッジ時間 | 9,661 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 |
ソースコード
import java.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.function.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
import static java.lang.Math.*;
import static java.lang.String.format;
public class Main {
public static void main(String[] args) {
solve();
}
final static int INF = Integer.MAX_VALUE >> 2;
final static int MOD = 1_000_000_007;
final static int[] dx4 = {0, 1, 0, -1};
final static int[] dy4 = {1, 0, -1, 0};
final static int[] dx9 = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
final static int[] dy9 = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
final static Runnable me = () -> {
};
public static void solve() {
//TODO:Solve problem like ***
final Scanner sc = new Scanner();
final int n = sc.nextInt();
final int q = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
int[][] cxy = new int[q][3];
for (int i = 0; i < q; i++) {
cxy[i][0] = sc.next().equals("A")?0:1;
cxy[i][1] = sc.nextInt();
cxy[i][2] = sc.nextInt();
}
SimpleBIT simpleBIT = new SimpleBIT(new long[n+1]);
long[] ans = new long[n];
for (int i = q - 1; i >= 0; i--) {
if(cxy[i][0]==0){
//"A"
ans[cxy[i][1]-1] += cxy[i][2] * simpleBIT.sum(cxy[i][1]-1);
}else{
//"B"
simpleBIT.add(cxy[i][1]-1,1);
simpleBIT.add(cxy[i][2],-1);
}
}
for (int i = 0; i < n; i++) {
ans[i] += a[i] * simpleBIT.sum(i);
}
put(Arrays.stream(ans).mapToObj(Long::toString).collect(Collectors.joining(" ")));
}
private final static class SimpleBIT{
private final long[] bit;
private final int n;
public SimpleBIT(long[] longs){
this.bit = Arrays.copyOf(longs, longs.length);
this.n = bit.length;
}
public void add(int index,int w){
//親ノードの添字は1-indexedの数値を使って計算する
for (int i = index, j = i + 1; i < n; j += j & -j, i = j - 1) {
bit[i]+=w;
}
}
/**
* v[0]+v[1]+...+v[last]
* @param last
* @return
*/
public long sum(int last){
long ret=0;
for (int i = last, j = i + 1; i >= 0; j -= j & -j, i = j - 1) {
ret += bit[i];
}
return ret;
}
/**
* 半開区間[begin,end)(endは含まない)
* @param begin
* @param end
* @return
*/
public long sum(int begin,int end){
if(begin>=end){
throw new IllegalArgumentException(String.format("it need begin(=%d) < end(=%d)", begin, end));
}
return sum(end - 1) - sum(begin);
}
}
static class Encoder {
final int mod;
public Encoder(int mod) {
this.mod = mod;
}
public int encode(int x, int y) {
assert y < mod;
return x * mod + y;
}
public int decodeX(int z) {
return z / mod;
}
public int decodeY(int z) {
return z % mod;
}
}
static class Accepter<T> {
private T val;
private final Predicate<T> p;
public Accepter(T defaultValue, Predicate<T> p) {
this.val = defaultValue;
this.p = p;
}
/**
* @return accepted newval?
*/
public boolean replace(T newVal) {
if (p.test(newVal)) {
this.val = newVal;
return true;
}
return false;
}
}
//runWhenEAで使う
private static Runnable func(Object... objects) {
try {
assert false;
return me;
} catch (AssertionError e) {
return () -> {
put(objects);
};
}
}
private static void print(Object... objects) {
if (objects.length == 1) {
System.out.print(objects[0]);
} else {
System.out.print(Arrays.toString(objects));
}
}
private static void put(Object... objects) {
print(objects);
put();
}
private static void put() {
System.out.println();
}
private static void runWhenEA(Runnable runnable) {
try {
assert false;
} catch (AssertionError e) {
PrintStream ps = System.out;
PrintStream pse = System.err;
System.setOut(pse);
runnable.run();
System.setOut(ps);
}
}
private static void putM(String name, char[][] mat) {
put("---------------------" + name + "-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name, int[][] mat) {
put("---------------------" + name + "-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name, long[][] mat) {
put("---------------------" + name + "-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static void putM(String name, boolean[][] mat) {
put("---------------------" + name + "-----------------");
for (int i = 0; i < mat.length; i++) {
put(Arrays.toString(mat[i]));
}
}
private static final 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;
}
ptr = 0;
try {
buflen = in.read(buffer);
} catch (IOException e) {
e.printStackTrace();
}
return buflen > 0;
}
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());
}
}
private static class FixedIntPair {
public final int x, y;
public static final FixedIntPair ZEROS = new FixedIntPair(0, 0);
FixedIntPair(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return format(FixedIntPair.class.getSimpleName() + ":(%d,%d)", x, y);
}
}
private static final class FixedLongPair {
public final long x, y;
public static final FixedLongPair ZEROS = new FixedLongPair(0, 0);
FixedLongPair(long x, long y) {
this.x = x;
this.y = y;
}
@Override
public int hashCode() {
return (int) x + (int) y;
}
@Override
public boolean equals(Object obj) {
if (obj == null) return false;
if (!(obj instanceof FixedLongPair)) return false;
FixedLongPair pair = (FixedLongPair) obj;
return this.x == pair.x && this.y == pair.y;
}
@Override
public String toString() {
return format(FixedLongPair.class.getSimpleName() + ":(%d,%d)", x, y);
}
}
private static final class Binary {
public static String toZeroPadding(int i) {
return format("%" + Integer.toBinaryString(-1).length() + "s", Integer.toBinaryString(i)).replace(' ', '0');
}
public static String toZeroPadding(long i) {
return format("%" + Long.toBinaryString(-1).length() + "s", Long.toBinaryString(i)).replace(' ', '0');
}
}
private static final class Util {
static long gcd(long a, long b) {
a = abs(a);
b = abs(b);
if (a < b) {
long tmp = a;
a = b;
b = tmp;
}
while (b != 0) {
long r = a % b;
a = b;
b = r;
}
return a;
}
static int gcd(int a, int b) {
a = abs(a);
b = abs(b);
if (a < b) {
int tmp = a;
a = b;
b = tmp;
}
while (b != 0) {
int r = a % b;
a = b;
b = r;
}
return a;
}
static long lcm(long a, long b) {
long gcd = gcd(a, b);
long result = b / gcd;
return a * result;
}
static boolean isValidCell(int i, int j, int h, int w) {
return i >= 0 && i < h && j >= 0 && j < w;
}
}
}
/*
......................................................................................................................................
..................................... ________ ____ __________________________________________ .....................................
..................................... / _____/| | \ \__ ___/\_ _____/\______ \.....................................
...................................../ \ ___| | / | \| | | __)_ | _/.....................................
.....................................\ \_\ \ | / | \ | | \ | | \.....................................
..................................... \______ /______/\____|__ /____| /_______ / |____|_ /.....................................
..................................... \/ \/ \/ \/ .....................................
......................................................................................................................................
.............................................................,;'';:...................................................................
........................................................+@@@@@@@@@@@@@@'..............................................................
.....................................................#@@@##############@@@:...........................................................
...................................................@@@####################@@,.........................................................
.................................................@@#########################@@........................................................
...............................................:@############################@@.......................................................
..............................................@@######@@@#';;'#@@@############@@:.....................................................
.............................................@#####@@,````````````,@@###########@:....................................................
............................................@####@;``````````````````+@##########@....................................................
...........................................@###@:``````````````````````#@########@@...................................................
..........................................@####``````````````````````````@########@@..................................................
.........................................###@.````````````````````````````@########@+.................................................
.........................................@#@```````````````````````````````#########@.................................................
........................................@#@`````````````````````````````````########@@................................................
.......................................,@@```````````````````````````````````@#######@:...............................................
.......................................@@`````````````````````````````````````@#######@...............................................
.......................................@:````````````````````#@@'``````````````@######@+..............................................
......................................#@```````````````````@@@@@@@#````````````########@..............................................
......................................@```````````````````@@@@@@@@@@````````````@######@+.............................................
......................................@``````````````````@@@@@@@+ +```````````+#######@.............................................
.....................................;:``````````````````@@@@@@@ @````````````@######@'............................................
.....................................@``````````````````:@@@@@@@ @````````````@#######@............................................
.....................................@```,@@@#``````````;@@@@@@@ @````````````:#######@:...........................................
.....................................@``@@@@@@@@````````.@@@@@@@# ,#`````````````@#######@...........................................
.....................................@`@@@@@@@+'@````````@@@@@@@@@@@``````````````@#######@...........................................
.....................................@,@@@@@@ ,```:+:``:@@@@@@@@@.``````````````@########@..........................................
.....................................#@@@@@@@ ;@@#;,,,@``:@@@@@@@````````````````#########@..........................................
.....................................+@@@@@@@@',,,,,,,,;,```.'+;``````````````````'########@;.........................................
.....................................'@@@@',,,,,,,,,,,,,@`````````````````````````:#########@.........................................
....................................:@#,,,,,:;;;;;:,,,,,@`````````````````````````.#########@.........................................
.................................:@#@@@@#++';;;;;;;;;;;;@``````````````````````````##########+........................................
...............................#@#+;;;;;;;;;;;;;;;;;;;;':``````````````````````````##########@........................................
....................................,@#@@@@@#+'';;;;;+@#```````````````````````````##########@........................................
.....................................@``````````.,,,.``````````````````````````````############.......................................
.....................................@`````````````````````````````````````````````#######+'+#@.......................................
.....................................@`````````````````````````````````````````````##########'@.......................................
.....................................#`````````````````````````````````````````````############@#.....................................
.....................................:.````````````````````````````````````````````##############@,...................................
......................................+```````````````````````````````````````````.###############@#..................................
......................................@```````````````````````````````````````````.################@@.................................
......................................@```````````````````````````````````````````.###+##############@................................
......................................@```````````````````````````````````````````.###+###############@...............................
......................................',``````````````````````````````````````````.####'##############@@..............................
.......................................@```````````````````````````````````````````#####+##############@:.............................
.......................................@```````````````````````````````````````````#####'###############@.............................
.......................................@```````````````````````````````````````````######'################............................
.......................................#,``````````````````````````````````````````#######'##############@............................
........................................@``````````````````````````````````````````@######++##############+...........................
........................................@``````````````````````````````````````````@#######'##############@...........................
........................................@``````````````````````````````````````````@########'#############@...........................
.......................................@#'`````````````````````````````````````````@#########'##############..........................
.......................................@#@`````````````````````````````````````````+#########+'############@..........................
......................................@##@`````````````````````````````````````````.##########+'###########@..........................
......................................@##@:`````````````````````````````````````````###########+'###########..........................
.....................................:@###@`````````````````````````````````````````@###########+'+#########,.........................
.....................................@####@`````````````````````````````````````````@#############''########..........................
.....................................@####@.````````````````````````````````````````;##############+'######@..........................
.....................................@#####@`````````````````````````````````````````################@@@###+..........................
.....................................@#####@`````````````````````````````````````````@###############@..;;............................
....................................,@#####@.````````````````````````````````````````+################'...............................
....................................:#######@`````````````````````````````````````````################@...............................
....................................:#######@`````````````````````````````````````````@###############@...............................
....................................,@#######,````````````````````````````````````````:###############@...............................
.....................................@######@@`````````````````````````````````````````@##############@...............................
.....................................@######@@`````````````````````````````````````````+##############@...............................
.....................................@#####@,;;`````````````````````````````````````````@#############@...............................
.....................................@####@@..@`````````````````````````````````````````+#############@...............................
.....................................,####@...@``````````````````````````````````````````@############+...............................
......................................@##@.....@`````````````````````````````````````````:###########@,...............................
.......................................@+......@``````````````````````````````````````````@##########@................................
...............................................:#``````````````````````````````````````````##########@................................
................................................@``````````````````````````````````````````+########@,................................
................................................'+``````````````````````````````````````````@#######@.................................
.................................................@```````````````````````````````````````````@#####@:.................................
.................................................'#``````````````````````````````````````````.#####@..................................
..................................................@```````````````````````````````````````````;###@...................................
...................................................@```````````````````````````````````````````+#@'...................................
...................................................'#```````````````````````````````````````````@#....................................
....................................................##`````````````````````````````````````````@#.....................................
.....................................................#@```````````````````````````````````````@+......................................
......................................................:@;```````````````````````````````````;@,.......................................
.......................................................;@@'```````````````````````````````:@@+;.......................................
.......................................................@,,'@@'``````````````````````````@@@,,,@.......................................
......................................................@,,,,,,'@@@@;````````````````.+@@@;,,,,,@.......................................
......................................................#@+@,,,,,,,,+@@@@@@@@@@@@@@@@@;,,,,,'@@@........................................
.........................................................+,,,#',,@@..............@,,,,,,,,@...........................................
..........................................................@@@,#@@,...............:+,,,'@,,@...........................................
..................................................................................@,,,@.##............................................
...................................................................................@;@................................................
....................................................................................:.................................................
......................................................................................................................................
......................................................................................................................................
*/