結果
| 問題 |
No.2395 区間二次変換一点取得
|
| コンテスト | |
| ユーザー |
 hiromi_ayase
|
| 提出日時 | 2023-07-28 22:09:41 |
| 言語 | Java (openjdk 23) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,051 bytes |
| コンパイル時間 | 2,717 ms |
| コンパイル使用メモリ | 83,812 KB |
| 実行使用メモリ | 57,276 KB |
| 最終ジャッジ日時 | 2024-10-06 19:04:57 |
| 合計ジャッジ時間 | 9,703 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 13 TLE * 1 -- * 6 |
ソースコード
import java.util.*;
@SuppressWarnings("unused")
public class Main {
static class SegmentTreeRSQ {
public int M, H, N;
public long[] st;
public long[] plus;
public SegmentTreeRSQ(int n) {
N = n;
M = Integer.highestOneBit(Math.max(N - 1, 1)) << 2;
H = M >>> 1;
st = new long[M];
plus = new long[H];
}
public SegmentTreeRSQ(int[] a) {
N = a.length;
M = Integer.highestOneBit(Math.max(N - 1, 1)) << 2;
H = M >>> 1;
st = new long[M];
plus = new long[H];
for (int i = 0; i < N; i++) {
st[H + i] = a[i];
}
for (int i = (M >> 1) - 1; i >= 1; i--) {
propagate(i);
}
}
public void add(int pos, int v) {
for (int i = H + pos; i >= 1; i >>>= 1) {
st[i] += v;
}
}
private void propagate(int i) {
int count = H / Integer.highestOneBit(i);
st[i] = st[2 * i] + st[2 * i + 1] + plus[i] * count;
}
public void add(int l, int r, int v) {
if (l < r)
add(l, r, v, 0, H, 1);
}
private void add(int l, int r, int v, int cl, int cr, int cur) {
if (cur >= H) {
st[cur] += v;
} else if (l <= cl && cr <= r) {
plus[cur] += v;
propagate(cur);
} else {
int mid = cl + cr >>> 1;
if (cl < r && l < mid) {
add(l, r, v, cl, mid, 2 * cur);
}
if (mid < r && l < cr) {
add(l, r, v, mid, cr, 2 * cur + 1);
}
propagate(cur);
}
}
private long gsum;
public long sum(int l, int r) {
gsum = 0;
sum(l, r, 0, H, 1);
return gsum;
}
private void sum(int l, int r, int cl, int cr, int cur) {
if (l <= cl && cr <= r) {
gsum += st[cur];
} else {
int mid = cl + cr >>> 1;
if (cl < r && l < mid) {
sum(l, r, cl, mid, 2 * cur);
}
if (mid < r && l < cr) {
sum(l, r, mid, cr, 2 * cur + 1);
}
gsum += plus[cur] * (Math.min(r, cr) - Math.max(l, cl));
}
}
}
private static void solve() {
int n = ni();
int b = ni();
int q = ni();
int[][] mat = {
{ 1, 0, 0, 0, 1 },
{ 0, 3, 2, 2, 0 },
{ 0, 0, 3, 0, 0 },
{ 0, 0, 3, 3, 0 },
{ 0, 0, 0, 0, 1 }
};
int[] a = {1, 1, 1, 1, 1};
var st = new SegmentTreeRSQ(n);
for (int i = 0; i < q; i++) {
int l = ni() - 1;
int m = ni() - 1;
int r = ni();
st.add(l, r, 1);
long k = st.sum(m, m + 1);
int[] ret = pow(mat, a, k, b);
out.println(ret[0] + " " + ret[1] + " " + ret[2]);
}
}
public static int[] pow(int[][] A, int[] v, long e, int mod) {
int[][] MUL = A;
for (int i = 0; i < v.length; i++)
v[i] %= mod;
for (; e > 0; e >>>= 1) {
if ((e & 1) == 1)
v = mul(MUL, v, mod);
MUL = p2(MUL, mod);
}
return v;
}
// int matrix * int vector
public static int[] mul(int[][] A, int[] v, int mod) {
int m = A.length;
int n = v.length;
int[] w = new int[m];
for (int i = 0; i < m; i++) {
long sum = 0;
for (int k = 0; k < n; k++) {
sum += (long) A[i][k] * v[k];
sum %= mod;
}
w[i] = (int) sum;
}
return w;
}
// int matrix^2 (cannot ensure negative values)
public static int[][] p2(int[][] A, int mod) {
int n = A.length;
int[][] C = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
long sum = 0;
for (int k = 0; k < n; k++) {
sum += (long) A[i][k] * A[k][j];
sum %= mod;
}
C[i][j] = (int) sum;
}
}
return C;
}
public static void main(String[] args) {
new Thread(null, new Runnable() {
@Override
public void run() {
long start = System.currentTimeMillis();
String debug = args.length > 0 ? args[0] : null;
if (debug != null) {
try {
is = java.nio.file.Files.newInputStream(java.nio.file.Paths.get(debug));
} catch (Exception e) {
throw new RuntimeException(e);
}
}
reader = new java.io.BufferedReader(new java.io.InputStreamReader(is), 32768);
solve();
out.flush();
tr((System.currentTimeMillis() - start) + "ms");
}
}, "", 64000000).start();
}
private static java.io.InputStream is = System.in;
private static java.io.PrintWriter out = new java.io.PrintWriter(System.out);
private static java.util.StringTokenizer tokenizer = null;
private static java.io.BufferedReader reader;
public static String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new java.util.StringTokenizer(reader.readLine());
} catch (Exception e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
private static double nd() {
return Double.parseDouble(next());
}
private static long nl() {
return Long.parseLong(next());
}
private static int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private static char[] ns() {
return next().toCharArray();
}
private static long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nl();
return a;
}
private static int[][] ntable(int n, int m) {
int[][] table = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table[i][j] = ni();
}
}
return table;
}
private static int[][] nlist(int n, int m) {
int[][] table = new int[m][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
table[j][i] = ni();
}
}
return table;
}
private static int ni() {
return Integer.parseInt(next());
}
private static void tr(Object... o) {
if (is != System.in)
System.out.println(java.util.Arrays.deepToString(o));
}
}