| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 894113 |
2023-12-28T01:18:31 Z |
CutSandstone |
Toll (BOI17_toll) |
Java 11 |
|
936 ms |
97104 KB |
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
import java.util.*;
public class toll {
// change to ur file
// for usaco only
private static final String name = "sprinklers2";
// constants to use
private static final int mod = 1_000_000_007, mm = 998244353, inf = Integer.MAX_VALUE;
private static final int[][] d4 = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
private static final long inf2 = Long.MAX_VALUE;
// need to generate Mod.fast(int max) first to use
private static long[] fact;
private static PrintWriter out;
private static FastIO sc;
private static long time = -1;
public static void main(String[] args) throws Exception {
// super giga brain reader that accounts for all platforms and displays time when its ur own platform
try {
if(name.length() != 0 && new File(name+".in").exists()) {
sc = new FastIO(name+".in");
out = new PrintWriter(name+".out");
}else if(new File("input.in").exists()){
sc = new FastIO("input.in");
// sc = new FastIO(System.in);
out = new PrintWriter(new BufferedOutputStream(System.out));
// out = new PrintWriter("input.text");
time = System.currentTimeMillis();
}else {
sc = new FastIO(System.in);
out = new PrintWriter(new BufferedOutputStream(System.out));
}
}catch(SecurityException e) {
sc = new FastIO(System.in);
out = new PrintWriter(new BufferedOutputStream(System.out));
}
// for(int T = sc.nextInt(); T>0; T--)
solve();
if(time != -1) System.out.println("Time: "+(System.currentTimeMillis()-time)+"ms");
out.close();
}
private static void solve() throws Exception {
int K = sc.nextInt(), N = sc.nextInt(), M = sc.nextInt(), Q = sc.nextInt();
List<Two<Integer, int[][]>>[] g = new List[(N-1)/K+1];
for(int i = 0; i<g.length; i++){
g[i] = new ArrayList<>(1);
if(i != 0){
int[][] next = new int[K][K];
g[i].add(new Two<>(i-1, next));
g[i-1].add(new Two<>(i, next));
for(int[] a: next) Arrays.fill(a, inf>>1);
}
}
while(M--> 0){
int a = sc.nextInt(), b = sc.nextInt(), t = sc.nextInt();
int c = b/K;
a%=K;
b%=K;
g[c].get(0).b[a][b] = min(g[c].get(0).b[a][b], t);
}
Jump<int[][]> jp = new Jump<>(g, (low, high) -> {
int[][] ans = new int[K][K];
for(int[] a: ans) Arrays.fill(a, inf>>1);
for(int i = 0; i<K; i++)
for(int j = 0; j<K; j++)
for(int m = 0; m<K; m++)
ans[i][j] = min(ans[i][j], high[i][m]+low[m][j]);
return ans;
});
while(Q--> 0){
int a = sc.nextInt(), b = sc.nextInt();
if(a == b){
out(0);
continue;
}
if(a/K == b/K){
out(-1);
continue;
}
int[][] ans = jp.jumpGet(b/K, b/K-a/K);
int ret = ans[a%K][b%K];
out(ret==inf>>1?-1:ret);
}
}
private static boolean prime(long num){
for(long i = 2; i*i<=num; i++) if(num%i == 0) return false;
return true;
}
// coord compression
private static void compress(int[]... nums) {
TreeMap<Integer, List<int[]>> s = new TreeMap<>();
for(int p = 0; p<nums.length; p++) for(int i = 0; i<nums[p].length; i++) {
List<int[]> get = s.get(nums[p][i]);
if(get == null) s.put(nums[p][i], get = new LinkedList<>());
get.add(new int[] {p, i});
}
int p = 0;
for(List<int[]> l: s.values()) {
for(int[] a: l) nums[a[0]][a[1]] = p;
p++;
}
}
// Mo's algorithm
private static class MoAlg<T, Edit, Quer> {
public interface Add<Edit, T> {public void add(Edit a, T curr, boolean first);}
public interface Rem<Edit, T> {public void rem(Edit a, T curr, boolean first);}
public interface Get<Edit, Quer> {public Object get(Edit a, Quer quer);}
private final T[] nums;
private final int block;
private final List<Two<int[], Quer>> quer;
private final Add<Edit, T> add;
private final Rem<Edit, T> rem;
private final Get<Edit, Quer> get;
private Edit def;
public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit, Quer> get, Edit def) {
this(nums, add, rem, get, def, -1);
}
public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit, Quer> get, Edit def, int Q) {
this.add = add;
this.rem = rem;
this.get = get;
this.nums = nums;
this.def = def;
block = (int)Math.sqrt(nums.length);
if(Q != -1) quer = new ArrayList<>(Q);
else quer = new ArrayList<>();
}
public void add(int l, int r, Quer curr) {
quer.add(new Two<>(new int[] {l, r, quer.size()}, curr));
}
public Object[] getAns() {
Collections.sort(quer, (a, b) -> a.a[0]/block == b.a[0]/block ? ((((a.a[0]/block)&1) == 0) ? a.a[1]-b.a[1]:b.a[1]-a.a[1]):a.a[0]-b.a[0]);
int l = 0, r = -1;
Object[] ans = new Object[quer.size()];
for(Two<int[], Quer> t: quer) {
int[] a = t.a;
if(r < a[0] || l > a[1]) {
for(int i = l; i<=r; i++) rem.rem(def, nums[i], true);
for(int i = a[0]; i<=a[1]; i++) add.add(def, nums[i], false);
}else {
if(l > a[0]) for(int i = l-1; i>=a[0]; i--) add.add(def, nums[i], true);
else for(int i = l; i<a[0]; i++) rem.rem(def, nums[i], true);
if(r > a[1]) for(int i = r; i>a[1]; i--) rem.rem(def, nums[i], false);
else for(int i = r+1; i<=a[1]; i++) add.add(def, nums[i], false);
}
l = a[0];
r = a[1];
ans[a[2]] = get.get(def, t.b);
}
return ans;
}
}
// combiners used for later
public interface Comb<Val>{Val oper(Val left, Val right);}
public interface Prop<Val, Lz> {Val oper(Lz top, Val current, long l, long r);}
public interface LZ<Lz>{Lz oper(Lz top, Lz current);}
public interface Def<Val>{Val get(long l, long r);}
public interface DefLz<Lz>{Lz get();}
private static int[][] hull(int[][] points) {
Arrays.sort(points, (o1, o2) -> o1[0] != o2[0] ? o1[0] - o2[0] : o1[1] - o2[1]);
int n = points.length;
boolean[] used = new boolean[n];
int[] hull = new int[n + 2];
int top = 0;
for (int i = 0; i < n; i++) {
while (top >= 2 && area(points[hull[top - 1]], points[hull[top]], points[i]) > 0) {
used[hull[top--]] = false;
}
hull[++top] = i;
used[i] = true;
}
used[0] = false;
for (int i = n - 1; i >= 0; i--) {
if (used[i]) continue;
while (top >= 2 && area(points[hull[top - 1]], points[hull[top]], points[i]) > 0) {
top--;
}
hull[++top] = i;
}
top--;
int[][] res = new int[top][2];
for (int i = 1; i <= top; i++) res[i - 1] = points[hull[i]];
return res;
}private static int area(int[] a, int[] b, int[] c) {
return cross(b[0] - a[0], b[1] - a[1], c[0] - a[0], c[1] - a[1]);
}private static int cross(int x1, int y1, int x2, int y2) {
return x1 * y2 - x2 * y1;
}
// dijkstra's
private static long[] minPath(int x, List<int[]>[] g) {
long[] l = new long[g.length];
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> Long.compare(l[a], l[b]));
Arrays.fill(l, Long.MAX_VALUE);
l[x] = 0;
pq.add(x);
while (!pq.isEmpty()) {
int c = pq.poll();
for (int[] a : g[c])
if (l[a[0]] > l[c] + a[1]) {
l[a[0]] = l[c] + a[1];
pq.add(a[0]);
}
}
return l;
}
// all the binary jumping/lifting stuff, Range stores the memory of each range
// Range combine is <lower, higher>
private static class Jump<Range> {
private final int[][] up;
private final int[] depth;
private int lg;
private final Comb<Range> comb;
private final Range[][] upMem;
public Jump(List<Integer>[] g) {
int N = g.length;
lg = 1;
while((1<<lg) <= N) lg++; lg++;
up = new int[N][lg];
depth = new int[N];
for(int[] a: up) Arrays.fill(a, -1);
dfs2(0, -1, g);
for(int i = 1; i<lg; i++) for(int j = 0; j<N; j++) if(up[j][i-1] != -1)
up[j][i] = up[up[j][i-1]][i-1];
upMem = null;
comb = null;
}
public Jump(List<Two<Integer, Range>>[] g, Comb<Range> comb) {
int N = g.length;
lg = 1;
while((1<<lg) <= N) lg++; lg++;
up = new int[N][lg];
this.comb = comb;
upMem = (Range[][]) new Object[N][lg];
depth = new int[N];
for(int[] a: up) Arrays.fill(a, -1);
dfs1(0, -1, g);
for(int i = 1; i<lg; i++) for(int j = 0; j<N; j++) if(up[j][i-1] != -1){
up[j][i] = up[up[j][i-1]][i-1];
if(up[j][i] != -1)
upMem[j][i] = comb.oper(upMem[j][i-1], upMem[up[j][i-1]][i-1]);
}
}
private void dfs2(int s, int p, List<Integer>[] g) {
up[s][0] = p;
for(int e: g[s]) if(e != p) {
depth[e] = depth[s]+1;
dfs2(e, s, g);
}
}
private void dfs1(int s, int p, List<Two<Integer, Range>>[] g) {
up[s][0] = p;
for(Two<Integer, Range> e: g[s]) if(e.a != p) {
depth[e.a] = depth[s]+1;
upMem[e.a][0] = e.b;
dfs1(e.a, s, g);
}
}
public int lca(int a, int b) {
if(depth[a] > depth[b]) {
int s = a;
a = b;
b = s;
}
b = jump(b, depth[b]-depth[a]);
if(a == b) return a;
for(int i = lg-1; i>=0; i--) if(up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
return up[a][0];
}
public int dis(int a, int b) {
return depth[a]+depth[b]-(depth[lca(a, b)]<<1);
}
public Two<Integer, Two<Range, Range>> lcaGet(int a, int b){
int l = lca(a, b);
return new Two<>(l, new Two<>(jumpGet(a, depth[a]-depth[l]), jumpGet(b, depth[b]-depth[l])));
}
public Range jumpGet(int a, int k) {
if(depth[a] < k) return null;
Range ans = null;
for(int i = 0; i<lg; i++) if((k&(1<<i)) != 0) {
if(ans == null) ans = upMem[a][i];
else ans = comb.oper(ans, upMem[a][i]);
a = up[a][i];
}
return ans;
}
public int jump(int a, int k) {
if(depth[a] < k) return -1;
for(int i = 0; i<lg; i++) if((k&(1<<i)) != 0)
a = up[a][i];
return a;
}
public int par(int a){return up[a][0];}
}
// heavy light decomposition
private static int[][] HLD(List<Integer>[] g){
int N = g.length;
int[] pos = new int[N], last = new int[N], cnt = new int[N];
dfsCNTHLD(g, cnt, 0, -1);
dfsHLD(g, pos, last, 0, 0, -1, cnt);
return new int[][] {pos, last};
}private static void dfsCNTHLD(List<Integer>[] g, int[] cnt, int s, int p) {
cnt[s] = 1;
for(int i: g[s]) if(i != p) {
dfsCNTHLD(g, cnt, i, s);
cnt[s]+=cnt[i];
}
}private static int dfsHLD(List<Integer>[] g, int[] pos, int[] last, int timer, int s, int p, int[] cnt) {
pos[s] = timer++;
int m = -1;
for(int i: g[s]) if(i != p)
if(m == -1 || cnt[i] > cnt[m]) m = i;
if(m == -1) return timer;
last[m] = last[s];
timer = dfsHLD(g, pos, last, timer, m, s, cnt);
for(int i: g[s]) if(i != p && i != m) {
last[i] = i;
timer = dfsHLD(g, pos, last, timer, i, s, cnt);
}
return timer;
}
// strongly connected components
private static List<List<Integer>> SCC(List<Integer>[] g) {
int N = g.length;
int[] disc = new int[N];
int[] low = new int[N];
Arrays.fill(disc, -1);
Arrays.fill(low, -1);
boolean stackMember[] = new boolean[N];
LinkedList<Integer> st = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
ans.add(new ArrayList<>());
for (int i = 0; i<N; i++)
if (disc[i] == -1)
SCCUtil(i, low, disc, stackMember, st, 0, g, ans);
ans.remove(ans.size()-1);
return ans;
}
private static int SCCUtil(int s, int[] low, int[] disc, boolean[] stackMember, LinkedList<Integer> st, int time, List<Integer>[] g, List<List<Integer>> ans) {
disc[s] = time;
low[s] = time;
time++;
stackMember[s] = true;
st.push(s);
for(int i: g[s]){
if (disc[i] == -1) {
time = SCCUtil(i, low, disc, stackMember, st, time, g, ans);
low[s] = min(low[s], low[i]);
} else if(stackMember[i] == true)
low[s] = min(low[s], disc[i]);
}
int w = -1;
if (low[s] == disc[s]) {
while (w != s) {
w = st.pop();
ans.get(ans.size()-1).add(w);
stackMember[w] = false;
}
ans.add(new ArrayList<>());
}
return time;
}
// depth of tree in arr[0], par of nodes in arr[1]
private static int[][] depthPar(int s, List<Integer>[] g) {
int[][] ans = new int[2][g.length];
depthParDFS(g, s, -1, ans);
return ans;
}
private static void depthParDFS(List<Integer>[] g, int s, int p, int[][] d) {
d[1][s] = p;
for(int i: g[s]) if(i != p) {
d[0][i] = d[0][s]+1;
depthParDFS(g, i, s, d);
}
}
// compresses nodes with 1 child
// new tree in arr[0], list of previous nodes that compress to new nodes in arr[1]
private static List<Integer>[][] treeComp(List<Integer>[] g){
int N = g.length;
if(N == 1) {
List<Integer>[][] ans = new List[2][1];
ans[0][0] = new LinkedList<>();
ans[1][0] = new LinkedList<>();
ans[1][0].add(0);
return ans;
}
int[] map = new int[N];
int K = treeCompGetCount(g, 0, -1, map, 0);
List<Integer>[][] ans = new List[2][K];
for(int i = 0; i<K; i++) {
ans[0][i] = new LinkedList<>();
ans[1][i] = new LinkedList<>();
}
treeCompDFS(g, map, ans, 0);
return ans;
}
private static int treeCompGetCount(List<Integer>[] g, int s, int p, int[] map, int time) {
g[s].remove((Integer)p);
if(p == -1 || g[p].size() != 1) map[s] = time++; else map[s] = -1;
for(int i: g[s]) if(i != p) time = treeCompGetCount(g, i, s, map, time);
return time;
}
private static void treeCompDFS(List<Integer>[] g, int[] map, List<Integer>[][] ret, int s) {
int curr = s;
while(g[curr].size() == 1) {
ret[1][map[s]].add(curr);
curr = g[curr].get(0);
}
ret[1][map[s]].add(curr);
for(int i: g[curr]) {
ret[0][map[s]].add(map[i]);
treeCompDFS(g, map, ret, i);
}
}
// detects cycle
private static boolean hasCycle(List<Integer>[] g) {
byte[] vis = new byte[g.length];
for(int i = 0; i<g.length; i++) if(vis[i] == 0 && hasCycleHelper(g, i, vis)) return true;
return false;
}
private static boolean hasCycleHelper(List<Integer>[] g, int s, byte[] vis) {
vis[s] = 1;
for(int i: g[s]) if(vis[i] == 1) return true;
else if(vis[i] == 0 && hasCycleHelper(g, i, vis)) return true;
vis[s] = 2;
return false;
}
//DSU but can store memory in each component
private static class DSU<Val> {
private Val[] vals;
private int[] par, size;
private Merge<Integer>[] all;
private int cc;
private Comb<Val> o;
public DSU(int N, boolean storeAll) {this(N, null, storeAll);}
public DSU(int N, Comb<Val> o) {this(N, o, false);}
public DSU(int N) {this(N, null, false);}
public DSU(int N, Comb<Val> o, boolean storeAll) {
par = new int[N];
size = new int[N];
cc = N;
Arrays.fill(par, -1);
Arrays.fill(size, 1);
this.o = o;
if(o != null) vals = (Val[]) new Object[N];
if(storeAll) {
all = new Merge[N];
for(int i = 0; i<N; i++) {
all[i] = new Merge();
all[i].add(i);
}
}
}
public Val getVal(int num) {
return vals[get(num)];
}
public int size(int num) {
return size[get(num)];
}
public int get(int num) {
return par[num] == -1 ? num : (par[num] = get(par[num]));
}
public boolean isSame(int x, int y) {
return get(x) == get(y);
}
public boolean unite(int x, int y) {
int p1 = get(x), p2 = get(y);
if (p1 == p2)
return false;
Val next = o == null ? null:o.oper(vals[p1], vals[p2]);
Merge<Integer> a = all == null ? null:all[p1], b = all == null ? null:all[p2];
if (size[p1] < size[p2]) {
int s = p2;
p2 = p1;
p1 = s;
Merge<Integer> v = a;
a = b;
b = v;
}
size[p1] += size[p2];
par[p2] = p1;
cc--;
if(vals != null) vals[p1] = next;
if(a != null)
a.addAll(b);
return true;
}
public int getCC() {
return cc;
}
public void set(int num, Val curr) {
vals[get(num)] = curr;
}
public Merge<Integer> getAll(int num) {
return all[get(num)];
}
}
// counts via hashmap
private static class HCnt<T> {
public HashMap<T, Long> map;
private long size;
public HCnt(){map = new HashMap<>();}
public HCnt(int sz){map = new HashMap<>(sz);}
public long get(T num){
return map.getOrDefault(num, 0L);
}
public void add(T num){
add(num, 1);
}
public void rem(T num){
add(num, -1);
}
public void rem(T num, int cnt){
add(num, -cnt);
}
public void add(T num, int cnt){
size+=cnt;
Long get = map.get(num);
if (get == null)
get = 0L;
get += cnt;
if (get == 0)
map.remove(num);
else
map.put(num, get);
}
public boolean isEmpty() {
if(map == null) return true;
return map.isEmpty();
}
public int distinct(){
return map == null ? 0:map.size();
}
public long size(){
return size;
}
@Override
public String toString() {
return map.toString();
}
}
// counts amount of numbers using treemap
private static class Cnt<T> {
public TreeMap<T, Long> map;
boolean first = true;
private long size;
public Cnt() {}
public long get(T num) {
if(first) {
if(num instanceof Long) map = new TreeMap<>((a, b) -> Long.compare((long)a, (long)b));
else map = new TreeMap<>();
first = false;
}
return map.getOrDefault(num, 0L);
}
public void add(T num) {
add(num, 1);
}
public void rem(T num) {
add(num, -1);
}
public void rem(T num, long cnt) {
add(num, -cnt);
}
public void add(T num, long cnt) {
size+=cnt;
if(first) {
if(num instanceof Long) map = new TreeMap<>((a, b) -> Long.compare((long)a, (long)b));
else map = new TreeMap<>();
first = false;
}
Long get = map.get(num);
if (get == null)
get = 0L;
get += cnt;
if (get == 0)
map.remove(num);
else
map.put(num, get);
}
public boolean isEmpty() {
if(map == null) return true;
return map.isEmpty();
}
public int distinct(){
return map == null ? 0:map.size();
}
public long size(){
return size;
}
public T min() {
if(map == null) return null;
return map.isEmpty() ? null:map.firstKey();
}
public T max() {
if(map == null) return null;
return map.isEmpty() ? null:map.lastKey();
}
@Override
public String toString() {
return map.toString();
}
}
// 1 line convenience functions
private static void print(int... a) {
if(time != -1) System.out.println(a == null ? "null":a.length == 0 ? "":Arrays.toString(a).replaceAll("2147483647", "inf"));
}
private static void print(long... a) {
if(time != -1) System.out.println(a == null ? "null":a.length == 0 ? "":Arrays.toString(a).replaceAll("9.223372036854776E18", "inf"));
}
private static void print(char x) {
if(time != -1) System.out.println(x);
}
private static void print(double d) {
if(time != -1) System.out.println(d);
}
private static void print(char[] c) {
if(time != -1) System.out.println(Arrays.toString(c));
}
private static void print() {
if(time != -1) System.out.println();
}
private static void print(String s) {
if(time != -1) System.out.println(s);
}
private static void print(boolean b) {
if(time != -1) System.out.println(b);
}
private static void print(Object o) {
if(time != -1) {
if(o instanceof Object[]) System.out.println(Arrays.toString((Object[])o));
else System.out.println(o);
}
}
private static void out(boolean... b){
for(boolean x: b) out.println(x?"Yes":"No");
}
private static void out(int... a) {
for(int i = 0; i<a.length; i++) out.print(a[i]+(i==a.length-1?"\n":" "));
}
private static void out(long... a) {
for(int i = 0; i<a.length; i++) out.print(a[i]+(i==a.length-1?"\n":" "));
}
private static void outLn(int... a) {
for(int i: a) out.println(i);
}
private static void outLn(long... a) {
for(long l: a) out.println(l);
}
// prime divisor
private static int[] divisor(int n){
int[] ans = new int[n+1];
for(int i = 2; i<=n; i++) if(ans[i] == 0)
for(int j = i; j<=n; j+=i) ans[j] = i;
return ans;
}
// check if primes
private static boolean[] primes(int n){
boolean[] ans = new boolean[n+1];
Arrays.fill(ans, true);
ans[0] = ans[1] = false;
for(int i = 2; i<=n; i++) if(ans[i])
for(int j = i<<1; j<=n; j+=i) ans[j] = false;
return ans;
}
// euler totient
private static int[] phi(int n){
int[] ans = new int[n+1];
for (int i = 0; i<=n; i++) ans[i] = i;
for(int i = 2; i<=n; i++) if(ans[i] == i)
for(int j = i; j<=n; j+=i) ans[j]-=ans[j]/i;
return ans;
}
// basic math
private static long lcm(long... arr) {
for(int i = 1; i<arr.length; i++)
arr[0] = arr[0]*(arr[i]/gcd(arr[0], arr[i]));
return arr[0];
}
private static long gcd(long... arr) {
long ans = arr[0];
for(int i = 1; i<arr.length; i++) {
long c = arr[i];
while(c != 0) {
long t = ans%c;
ans = c;
c = t;
}
}
return ans;
}
private static int abs(int x){
return x<0?-x:x;
}
private static long abs(long x){
return x<0?-x:x;
}
private static int max(int... x) {
int ans = x[0];
for (int i = 1; i < x.length; i++)
ans = Math.max(ans, x[i]);
return ans;
}
private static int min(int... x) {
int ans = x[0];
for (int i = 1; i < x.length; i++)
ans = Math.min(ans, x[i]);
return ans;
}
private static long max(long... x) {
long ans = x[0];
for (int i = 1; i < x.length; i++)
ans = Math.max(ans, x[i]);
return ans;
}
private static long min(long... x) {
long ans = x[0];
for (int i = 1; i < x.length; i++)
ans = Math.min(ans, x[i]);
return ans;
}
// modular arithmatic
private static class Mod {
static long mod = toll.mod;
private Mod() {
}
public static void setMod(long m){mod = m;}
public static void fact(int max) {
fact = new long[max+1];
fact[0] = 1;
for(int i = 1; i<=max; i++) fact[i] = (fact[i-1]*i)%mod;
}
public static long nCk(int n, int k) {
return (fact[n]*((inv(fact[k])*inv(fact[n-k])%mod)))%mod;
}
public static long nPk(int n, int k){
return fact[n]*inv(fact[n-k])%mod;
}
public static long mul(long a, long b, long mod) {
long ret = 0;
while(b > 0) {
if((b&1) == 1)
ret = (ret+a)%mod;
a = (a<<1)%mod;
b>>=1;
}
return ret;
}
public static long inv(long x) {
return pow(x, mod - 2);
}
public static long pow(long x, long n) {
x %= mod;
long res = 1;
while (n > 0) {
if ((n & 1) == 1)
res = res * x % mod;
x = x * x % mod;
n >>= 1;
}
return res;
}
}
// binary search (last true, first true)
private static class BS {
public interface Oper {
boolean test(long num);
}
public interface IntOper {
boolean test(int num);
}
private BS() {
}
public static long lastLong(long lo, long hi, Oper oper) {
lo--;
while (lo < hi) {
long mid = lo+((hi-lo+1)>>1);
if (oper.test(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
public static int lastInt(int lo, int hi, IntOper oper) {
lo--;
while (lo < hi) {
int mid = lo+((hi-lo+1)>>1);
if (oper.test(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
public static long firstLong(long lo, long hi, Oper oper) {
hi++;
while (lo < hi) {
long mid = lo+((hi-lo)>>1);
if (oper.test(mid)) hi = mid;
else lo = mid+1;
}
return lo;
}
public static int firstInt(int lo, int hi, IntOper oper) {
hi++;
while (lo < hi) {
int mid = lo+((hi-lo)>>1);
if (oper.test(mid)) hi = mid;
else lo = mid+1;
}
return lo;
}
}
// linked lists that can merge in O(1)
private static class Merge<T> implements Iterable<T> {
private class Node {
public T num;
public Node next = null;
public Node(T num) {
this.num = num;
}
}
private class mergeIterator implements Iterator<T> {
private Node s;
public mergeIterator(Node s) {
this.s = s;
}
@Override
public boolean hasNext() {
return s != null;
}
@Override
public T next() {
T ret = s.num;
s = s.next;
return ret;
}
}
private Node s, e;
private int size;
public Merge() {
s = e = null;
size = 0;
}
public void addF(T n) {
if (s == null)
s = e = new Node(n);
else {
Node p = new Node(n);
p.next = s;
s = p;
}
size++;
}
public void add(T n) {
if (s == null)
s = e = new Node(n);
else {
e.next = new Node(n);
e = e.next;
}
size++;
}
public void addAll(Merge<T> m) {
if (m == this)
return;
if (e == null)
s = e = m.s;
else
e.next = m.s;
e = m.e;
size += m.size;
}
public int size() {
return size;
}
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (T i : this)
sb.append(i + ", ");
if (sb.length() > 1)
sb.delete(sb.length() - 2, sb.length());
sb.append("]");
return sb.toString();
}
@Override
public Iterator<T> iterator() {
return new mergeIterator(s);
}
public void clear() {
s = e = null;
size = 0;
}
}
// pairs 2 objects into 1 (can be used in hashmap)
private static class Two<A, B> {
public A a;
public B b;
public Two(A a, B b) {
this.a = a;
this.b = b;
}
@Override
public boolean equals(Object obj) {
if (!(obj instanceof Two))
return false;
Two curr = (Two) obj;
return curr.a.equals(a) && curr.b.equals(b);
}
@Override
public int hashCode() {
long seed = a.hashCode();
seed = seed << 32;
seed |= b.hashCode();
Random r = new Random();
r.setSeed(seed);
return r.nextInt();
}
@Override
public String toString() {
return "(" + (a==null?"null":a.toString()) + ", " + (b==null?"null":b.toString()) + ")";
}
}
// range add, point query
private static class RevBIT {
private final long[] bit;
private final long[] arr;
public final int len;
private long add;
public RevBIT(int len) {
bit = new long[len + 1];
arr = new long[len];
this.len = len;
add = 0;
}
public void set(int ind, long val) {
add(ind, ind, val - get(ind));
}
public void add(int s, int e, long val) {
if(s == 0 && e == len-1) {
add+=val;
return;
}
add(s, val);
if (e != len - 1)
add(e + 1, -val);
}
public void addAll(long val) {add+=val;}
private void add(int ind, long val) {
arr[ind] += val;
ind++;
for (; ind <= len; ind += ind & -ind)
bit[ind] += val;
}
public long diff(int ind) {
return arr[ind];
}
public long get(int ind) {
ind++;
long sum = 0;
for (; ind > 0; ind -= ind & -ind)
sum += bit[ind];
return sum+add;
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for (int i = 0; i < len; i++)
ret.append(get(i) + (i == len - 1 ? "]" : ", "));
return ret.toString();
}
}
// Lazy segment tree for all operations (sparse)
private static class ALST<Val, Lz> {
private final long l, r;
private ALST<Val, Lz> left, right;
private Val val;
private Lz lz;
private final Def<Val> def;
private final DefLz<Lz> defLz;
private Comb<Val> comb;
private Prop<Val, Lz> prop;
private LZ<Lz> lzOper;
public ALST(long N, Comb<Val> comb, Prop<Val, Lz> prop, LZ<Lz> lzOper, Def<Val> def, DefLz<Lz> defLz)
{this(0, N-1, comb, prop, lzOper, def, defLz);}
private ALST(long l, long r, Comb<Val> comb, Prop<Val, Lz> prop, LZ<Lz> lzOper, Def<Val> def, DefLz<Lz> defLz) {
this.l = l;
this.r = r;
this.comb = comb;
this.prop = prop;
this.lzOper = lzOper;
val = def.get(l, r);
lz = defLz.get();
this.def = def;
this.defLz = defLz;
}
public Val all() {
return val;
}
public void push(long s, Lz num) {push(s, s, num);}
public void push(long a, long b, Lz num) {
if(a == l && b == r) {push(num); return;}
long mid = (l+r)>>1;
if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
prop();
if(b <= mid) left.push(a, b, num);
else if(a > mid) right.push(a, b, num);
else {
left.push(a, mid, num);
right.push(mid+1, b, num);
}
val = comb.oper(left.val, right.val);
}
public void set(long s, Val num) {
if(l == r) {
val = num;
return;
}
long mid = (l+r)>>1;
if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
prop();
if(s > mid) right.set(s, num);
else left.set(s, num);
val = comb.oper(left.val, right.val);
}
public Val get(long a, long b) {
if(a == l && b == r) return all();
long mid = (l+r)>>1;
if(left == null) left = new ALST<Val, Lz>(l, mid, comb, prop, lzOper, def, defLz);
if(right == null) right = new ALST<Val, Lz>(mid+1, r, comb, prop, lzOper, def, defLz);
prop();
if(b <= mid) return left.get(a, b);
if(a > mid) return right.get(a, b);
return comb.oper(left.get(a, mid), right.get(mid+1, b));
}
private void prop() {
left.push(lz);
right.push(lz);
lz = defLz.get();
}
private void push(Lz num) {
lz = lzOper.oper(num, lz);
val = prop.oper(num, val, l, r);
}
}
// Lazy segment tree for add, set, max, min, sum (sparse)
private static class LZST {
private class Node {
public long l, r;
public Node left, right;
public long val = 0, max = 0, min = 0, add = 0;
public boolean isSet = false;
public Node(long a, long b) {
l = a;
r = b;
}
public void set(long num) {
isSet = true;
add = max = min = num;
val = num*(r-l+1);
}
public void add(long num) {
add+=num;
val+=num*(r-l+1);
max+=num;
min+=num;
}
public void prop() {
long mid = (l+r)>>1;
if(left == null) left = new Node(l, mid);
if(right == null) right = new Node(mid+1, r);
if(isSet) {
isSet = false;
if(l != r) {
left.set(add);
right.set(add);
}
}else if(add != 0) {
if(l != r) {
left.add(add);
right.add(add);
}
}
add = 0;
}
public void upd() {
val = left.val+right.val;
min = Math.min(left.min, right.min);
max = Math.max(left.max, right.max);
}
}
Node top;
public LZST(long N) {
assert(N > 0);
top = new Node(0, N-1);
}
private void set(long s, long e, long num, Node curr) {
if(curr.l == s && curr.r == e) {
curr.set(num);
return;
}
curr.prop();
if(e <= curr.left.r) set(s, e, num, curr.left);
else if(s >= curr.right.l) set(s, e, num, curr.right);
else{
set(s, curr.left.r, num, curr.left);
set(curr.right.l, e, num, curr.right);
}
curr.upd();
}
private void add(long s, long e, long num, Node curr) {
if(curr.l == s && curr.r == e) {
curr.add(num);
return;
}
curr.prop();
if(e <= curr.left.r) add(s, e, num, curr.left);
else if(s >= curr.right.l) add(s, e, num, curr.right);
else{
add(s, curr.left.r, num, curr.left);
add(curr.right.l, e, num, curr.right);
}
curr.upd();
}
private long sum(long s, long e, Node curr) {
if(curr.l == s && curr.r == e) return curr.val;
curr.prop();
if(e <= curr.left.r) return sum(s, e, curr.left);
if(s >= curr.right.l) return sum(s, e, curr.right);
return sum(s, curr.left.r, curr.left)+sum(curr.right.l, e, curr.right);
}
private long max(long s, long e, Node curr) {
if(curr.l == s && curr.r == e) return curr.max;
curr.prop();
if(e <= curr.left.r) return max(s, e, curr.left);
if(s >= curr.right.l) return max(s, e, curr.right);
return Math.max(max(s, curr.left.r, curr.left), max(curr.right.l, e, curr.right));
}
private long min(long s, long e, Node curr) {
if(curr.l == s && curr.r == e) return curr.min;
curr.prop();
if(e <= curr.left.r) return min(s, e, curr.left);
if(s >= curr.right.l) return min(s, e, curr.right);
return Math.min(min(s, curr.left.r, curr.left), min(curr.right.l, e, curr.right));
}
public long get(long s) {
assert(s >= top.l && s <= top.r);
Node curr = top;
LinkedList<Node> stk = new LinkedList<>();
while(curr.l != curr.r) {
stk.push(curr);
curr.prop();
if(s <= curr.left.r) curr = curr.left;
else curr = curr.right;
}
while(!stk.isEmpty()) stk.pop().upd();
return curr.val;
}
public long sum(long s, long e) {
assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
return sum(s, e, top);
}
public long max(long s, long e) {
assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
return max(s, e, top);
}
public long min(long s, long e) {
assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
return min(s, e, top);
}
public void add(long s, long e, long num) {
assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
add(s, e, num, top);
}
public void add(long s, long num) {
assert(s >= top.l && s <= top.r);
add(s, s, num);
}
public void set(long s, long e, long num) {
assert(s >= top.l && s <= top.r && e >= top.l && e <= top.r && s <= e);
set(s, e, num, top);
}
public void set(long s, long num) {
assert(s >= top.l && s <= top.r);
set(s, s, num);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[");
for(int i = 0; i<=top.r; i++) sb.append(get(i)+(i == top.r ? "]":", "));
return sb.toString();
}
}
// sparse segment tree with all associative operations
private static class AST<Val> {
private class Node<Val> {
public Val val;
public Node<Val> p, le, ri;
public long l, r;
public Node(long l, long r, Def<Val> def, Node<Val> p) {
this.l = l;
this.r = r;
this.p = p;
val = def.get(l, r);
}
}
private final Comb<Val> oper;
private final Node<Val> top;
private final Def<Val> def;
private long prevNum = -1;
private Val prevVal = null;
public AST(long n, Comb<Val> oper) {this(n, oper, (l, r) -> null);}
public AST(long n, Comb<Val> oper, Def<Val> def) {
this.oper = oper;
top = new Node<>(0, n-1, def, null);
this.def = def;
}
public void set(long k, Val num) {
prevNum = k;
prevVal = num;
Node<Val> t = top;
while(t.l != t.r) {
long mid = (t.l+t.r)>>1;
if(t.le == null) {
t.le = new Node<>(t.l, mid, def, t);
t.ri = new Node<>(mid+1, t.r, def, t);
}
if(mid >= k) t = t.le;
else t = t.ri;
}
t.val = num;
t = t.p;
while (t != null) {
if(t.le.val == null || t.ri.val == null) return;
t.val = oper.oper(t.le.val, t.ri.val);
t = t.p;
}
}
public Val all() {
return top.val;
}
public Val get(long a) {
if(a == prevNum) return prevVal;
Node<Val> t = top;
while(t.l != t.r) {
if(t.le == null) return def.get(a, a);
if(t.le.r >= a) t = t.le;
else t = t.ri;
}
return t.val;
}
public Val get(long a, long b) {
if (a == b)
return get(a);
if(a > b) {
long s = a;
a = b;
b = s;
}
return get(a, b, top);
}
private Val get(long a, long b, Node<Val> n) {
if(n == null) return def.get(a, b);
if (a == n.l && b == n.r)
return n.val;
long mid = (n.l+n.r)>>1;
if(b <= mid) return get(a, b, n.le);
if(a > mid) return get(a, b, n.ri);
Val left = get(a, mid, n.le), right = get(mid+1, b, n.ri);
return oper.oper(left, right);
}
}
// segtree sparse point add range sum
private static class STAdd {
private long l, r, mid, sum;
private STAdd left, right;
public STAdd(long N) {this(0, N-1);}
private STAdd(long l, long r) {
this.l = l;
this.r = r;
mid = (l+r)>>1;
sum = 0;
}
private STAdd left() {
if(left != null) return left;
return left = new STAdd(l, mid);
}
private STAdd right() {
if(right != null) return right;
return right = new STAdd(mid+1, r);
}
public void add(long s, long val) {
sum+=val;
if(l != r) {
if(s > mid) right().add(s, val);
else left().add(s, val);
}
}
public long sum(long s, long e) {
if(e < s) {
long t = s;
s = e;
e = t;
}
return sum(s, e, true);
}
private long sum(long s, long e, boolean dummy) {
if(s == l && e == r) return sum;
if(s > mid) {
if(right == null) return 0;
return right.sum(s, e, true);
}
if(e <= mid) {
if(left == null) return 0;
return left.sum(s, e, true);
}
long l = left == null ? 0:left.sum(s, mid, true);
long r = right == null ? 0:right.sum(mid+1, e, true);
return l+r;
}
}
// 2d segtree sparse point add range sum
private static class ST2DAdd {
private long l, r, mid, N;
private STAdd sum;
private ST2DAdd left, right;
public ST2DAdd(long N) {
this(0, N-1, N);
}
public ST2DAdd(long A, long B) {
this(0, A-1, B);
}
private ST2DAdd(long l, long r, long N) {
sum = new STAdd(N);
this.l = l;
this.r = r;
this.N = N;
mid = (l+r)>>1;
}
private ST2DAdd left() {
if(left != null) return left;
return left = new ST2DAdd(l, mid, N);
}
private ST2DAdd right() {
if(right != null) return right;
return right = new ST2DAdd(mid+1, r, N);
}
public void add(long x, long y, long val) {
sum.add(y, val);
if(l != r) {
if(x > mid) right().add(x, y, val);
else left().add(x, y, val);
}
}
public long sum(long x1, long y1, long x2, long y2) {
if(x1 > x2) {
long s = x1;
x1 = x2;
x2 = s;
}
if(y1 > y2) {
long s = y1;
y1 = y2;
y2 = s;
}
return sum(x1, y1, x2, y2, true);
}
private long sum(long x1, long y1, long x2, long y2, boolean dummy) {
if(x1 == l && x2 == r) return sum.sum(y1, y2, true);
if(x1 > mid) {
if(right == null) return 0;
return right.sum(x1, y1, x2, y2, true);
}
if(x2 <= mid) {
if(left == null) return 0;
return left.sum(x1, y1, x2, y2, true);
}
long l = left == null ? 0:left.sum(x1, y1, mid, y2, true);
long r = right == null ? 0:right.sum(mid+1, y1, x2, y2, true);
return l+r;
}
}
// 2d segtree sparse point update range (cummuative) query
private static class ST2D<Val> {
private static class Node<Val> {
public long l, r;
public Node<Val> left, right, par;
public AST<Val> val;
public Node(long l, long r, Node<Val> par, Comb<Val> oper, Def<Val> def, long N) {
this.l = l;
this.r = r;
this.par = par;
val = new AST<>(N, oper, def);
}
}
private final long N;
private final Comb<Val> oper;
private final Def<Val> def;
private final Node<Val> top;
public ST2D(long A, long B, Comb<Val> oper, Def<Val> def) {
this.oper = oper;
this.N = B;
this.def = def;
top = new Node<>(0, A-1, null, oper, def, N);
top.val = new AST<>(B, oper, def);
}
public ST2D(long N, Comb<Val> oper, Def<Val> def) {
this(N, N, oper, def);
}
public void set(long x, long y, Val num) {
Node<Val> curr = top;
while(curr.l != curr.r) {
long mid = (curr.l+curr.r)>>1;
if(curr.left == null) {
curr.left = new Node<>(curr.l, mid, curr, oper, def, N);
curr.right = new Node<>(mid+1, curr.r, curr, oper, def, N);
}
if(x > mid) curr = curr.right;
else curr = curr.left;
}
curr.val.set(y, num);
curr = curr.par;
while(curr != null) {
AST<Val> l = curr.left.val, r = curr.right.val;
curr.val.set(y, oper.oper(l.get(y), r.get(y)));
curr = curr.par;
}
}
public Val get(long x, long y) {
Node<Val> curr = top;
while(curr.l != curr.r) {
long mid = (curr.l+curr.r)>>1;
if(curr.left == null) {
curr.left = new Node<>(curr.l, mid, curr, oper, def, N);
curr.right = new Node<>(mid+1, curr.r, curr, oper, def, N);
}
if(x > mid) curr = curr.right;
else curr = curr.left;
}
AST<Val> c = curr.val;
return c.get(y);
}
public Val get(long x1, long y1, long x2, long y2) {
if(x1 > x2) {
long s = x1;
x1 = x2;
x2 = s;
}
return get(x1, y1, x2, y2, top);
}
private Val get(long x1, long y1, long x2, long y2, Node<Val> curr) {
if (x1 == curr.l && x2 == curr.r)
return curr.val.get(y1, y2);
long mid = (curr.l+curr.r) >> 1;
if (curr.left == null) {
curr.left = new Node<>(curr.l, mid, curr, oper, def, N);
curr.right = new Node<>(mid+1, curr.r, curr, oper, def, N);
}
if (x2 <= mid)
return get(x1, y1, x2, y2, curr.left);
if (x1 > mid)
return get(x1, y1, x2, y2, curr.right);
return oper.oper(get(x1, y1, mid, y2, curr.left), get(mid + 1, y1, x2, y2, curr.right));
}
}
// binary indexed tree (just sum)
private static class BIT {
private final long[] bit;
private final int len;
private long all;
public BIT(int len) {
bit = new long[len + 1];
this.len = len;
all = 0;
}
public long get(int ind) {return sum(ind, ind);}
public void set(int ind, long val) {add(ind, val-get(ind));}
public void add(int ind, long val) {
all+=val;
for(ind++; ind <= len; ind += ind & -ind) bit[ind] += val;
}
public long suf(int ind) {
return all-(ind == 0 ? 0:prev(ind-1));
}
public long prev(int ind) {
if(ind == len-1) return all;
long sum = 0;
for (ind++; ind > 0; ind -= ind & -ind) sum += bit[ind];
return sum;
}
public long sum(int a, int b) {
return prev(b) - (a == 0 ? 0 : prev(a - 1));
}
@Override
public String toString() {
StringBuilder ret = new StringBuilder();
ret.append("[");
for(int i = 0; i<len; i++) ret.append(get(i)+(i == len-1 ? "]":", "));
return ret.toString();
}
}
// 2d BIT
private static class BIT2D {
private final long[][] bit;
private final int A, B;
public BIT2D(int N) {this(N, N);}
public BIT2D(int A, int B) {
bit = new long[A+1][B+1];
this.A = A;
this.B = B;
}
public void add(int x, int y, long num) {
for(x++; x<=A; x+=x&-x)
for(int i = y+1; i<=B; i+=i&-i)
bit[x][i]+=num;
}
public long sum(int x, int y) {
long ans = 0;
for(x++; x>0; x-=x&-x)
for(int i = y+1; i>0; i-=i&-i)
ans+=bit[x][i];
return ans;
}
public long sum(int x1, int y1, int x2, int y2) {
return sum(x2, y2)-(x1 == 0 ? 0:sum(x1-1, y2))-(y1 == 0 ? 0:sum(x2, y1-1))+(x1 == 0 || y1 == 0 ? 0:sum(x1-1, y1-1));
}
}
// static range queries (logn preprocessing, constant query)
private static class SRQ<T> {
private static int lg(int n) { return 31 - Integer.numberOfLeadingZeros(n); }
private T[][] data;
private T[] nums;
private Comb<T> oper;
public SRQ(T[] nums, Comb<T> oper) {
this.nums = nums;
this.oper = oper;
int n = nums.length;
int logn = lg(n) + 1;
data = (T[][]) new Object[logn][n];
for(int k = 1; k <= n; k++) {
int rad = 1, i = 0;
while(k % (2 * rad) == 0) {
rad *= 2;
i++;
}
data[i][k - 1] = nums[k - 1];
for(int j = k - 2; j >= k - rad; j--)
data[i][j] = oper.oper(nums[j], data[i][j + 1]);
if(k < n) data[i][k] = nums[k];
for(int j = k + 1; j < n && j < k + rad; j++)
data[i][j] = oper.oper(data[i][j - 1], nums[j]);
}
}
public T get(int l, int r) {
if(l == r) return nums[l];
int ind = lg(l^r);
return oper.oper(data[ind][l], data[ind][r]);
}
}
// normal segment tree (order dosen't matter)
private static class ST {
public interface Oper {
long solve(long a, long b);
}
private long[] tree;
public final int n;
private final Oper oper;
private final long def;
public ST(int n, Oper oper, long def) {
this.n = n;
tree = new long[n << 1];
this.oper = oper;
this.def = def;
for (int i = 0; i < n; i++)
set(i, def);
}
public ST(int n, Oper oper) {
this(n, oper, 0);
}
public ST(int n) {
this(n, (a, b) -> Math.min(a, b), inf);
}
public long get(int a, int b) {
if (a == b)
return tree[a + n];
if (b < a)
return def;
a += n;
b += n;
long curr = 0;
boolean checked = false;
while (a <= b) {
if ((a & 1) == 1) {
if (checked)
curr = oper.solve(curr, tree[a++]);
else
curr = tree[a++];
checked = true;
}
if ((b & 1) == 0) {
if (checked)
curr = oper.solve(curr, tree[b--]);
else
curr = tree[b--];
checked = true;
}
a = a >> 1;
b = b >> 1;
}
return curr;
}
public long all() {
return get(0, n-1);
}
public void set(int index, long val) {
index += n;
tree[index] = val;
for (index = index >> 1; index >= 1; index = index >> 1)
tree[index] = oper.solve(tree[index << 1], tree[(index << 1) + 1]);
}
public long get(int index) {
return tree[index + n];
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("[");
for (int i = 0; i < n; i++) {
sb.append(get(i));
if (i != n - 1)
sb.append(", ");
}
sb.append("]");
return sb.toString();
}
}
// Range add, range sum
private static class RURQ {
private BIT b1, b2;
private int N;
public RURQ(int N) {
b1 = new BIT(N);
b2 = new BIT(N);
this.N = N;
}
public long prev(int x){
return b1.prev(x)*x-b2.prev(x);
}
public void add(int ind, long val){add(ind, ind, val);}
public void add(int l, int r, long val){
b1.add(l, val);
b2.add(l, val*(l-1));
if(r != N-1) {
b1.add(r+1, -val);
b2.add(r+1, -val*r);
}
}
public long get(int ind){return sum(ind, ind);}
public long sum(int l, int r){
return prev(r)-(l == 0 ? 0:prev(l-1));
}
}
// FastIO reader
private static class FastIO {
InputStream dis;
byte[] buffer = new byte[1<<22];
int pointer = 0, end = 0;
public FastIO(String fileName) throws Exception {
dis = new FileInputStream(fileName);
}
public char nextChar() throws Exception {
byte b;
do {
b = nextByte();
} while (b <= ' ');
return (char)b;
}
public FastIO(InputStream is) throws Exception {
dis = is;
}
public int nextInt() throws Exception {
int ret = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
ret = 10 * ret + b - '0';
b = nextByte();
}
return (negative) ? -ret : ret;
}
public long nextLong() throws Exception {
long ret = 0;
byte b;
do {
b = nextByte();
} while (b <= ' ');
boolean negative = false;
if (b == '-') {
negative = true;
b = nextByte();
}
while (b >= '0' && b <= '9') {
ret = 10 * ret + b - '0';
b = nextByte();
}
return (negative) ? -ret : ret;
}
private byte nextByte() throws Exception {
while (pointer >= end) {
end = dis.read(buffer, 0, buffer.length);
pointer = 0;
}
return buffer[pointer++];
}
public double nextDouble() throws Exception {
return Double.parseDouble(next());
}
public String next() throws Exception {
StringBuffer ret = new StringBuffer();
byte b;
do {
b = nextByte();
} while (b <= ' ');
while (b > ' ') {
ret.appendCodePoint(b);
b = nextByte();
}
return ret.toString();
}
public long[] longArr(int len) throws Exception{
long[] ans = new long[len];
for (int i = 0; i < len; i++)
ans[i] = nextLong();
return ans;
}
public int[] nextArr() throws Exception {
return nextArr(nextInt());
}
public int[] minusArr() throws Exception{
return minusArr(sc.nextInt());
}
public int[] minusArr(int N) throws Exception{
int[] arr = nextArr(N);
for(int i = 0; i<N; i++) --arr[i];
return arr;
}
public int[][] nextArr(int N, int M) throws Exception{
int[][] ans = new int[N][];
for(int i = 0; i<N; i++) ans[i] = nextArr(M);
return ans;
}
public int[] nextArr(int len) throws Exception {
int[] ans = new int[len];
for (int i = 0; i < len; i++)
ans[i] = nextInt();
return ans;
}
public List<Integer>[] nextTree() throws Exception {
return nextTree(nextInt());
}
public LinkedList<Integer>[] nextTree(int n) throws Exception {
return nextGraph(n, n - 1);
}
public LinkedList<int[]>[] weightGraph(int n, int m) throws Exception{
return weightGraph(n, m, false);
}
public LinkedList<int[]>[] weightGraph(int n, int m, boolean directed) throws Exception {
LinkedList<int[]>[] ans = new LinkedList[n];
for(int i = 0; i<n; i++) ans[i] = new LinkedList<>();
for(int i = 0; i<m; i++) {
int a = nextInt()-1, b = nextInt()-1, w = nextInt();
ans[a].add(new int[] {b, w});
if(!directed) ans[b].add(new int[] {a, w});
}
return ans;
}
public LinkedList<Integer>[] nextGraph(int n, int m) throws Exception {
return nextGraph(n, m, false);
}
public LinkedList<Integer>[] nextGraph(int n, int m, boolean directed) throws Exception {
LinkedList<Integer>[] ans = new LinkedList[n];
for (int i = 0; i < n; i++)
ans[i] = new LinkedList<>();
for (int i = 0; i < m; i++) {
int a = nextInt() - 1, b = nextInt() - 1;
ans[a].add(b);
if(!directed) ans[b].add(a);
}
return ans;
}
public char[] chars() throws Exception {
return next().toCharArray();
}
}
}
Compilation message
Note: toll.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
936 ms |
94400 KB |
Output is correct |
| 2 |
Correct |
104 ms |
32980 KB |
Output is correct |
| 3 |
Correct |
108 ms |
33216 KB |
Output is correct |
| 4 |
Correct |
107 ms |
33028 KB |
Output is correct |
| 5 |
Correct |
154 ms |
33984 KB |
Output is correct |
| 6 |
Correct |
146 ms |
34432 KB |
Output is correct |
| 7 |
Correct |
169 ms |
30440 KB |
Output is correct |
| 8 |
Correct |
932 ms |
94216 KB |
Output is correct |
| 9 |
Correct |
887 ms |
94648 KB |
Output is correct |
| 10 |
Correct |
845 ms |
94388 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
692 ms |
73060 KB |
Output is correct |
| 2 |
Correct |
108 ms |
32768 KB |
Output is correct |
| 3 |
Correct |
103 ms |
29640 KB |
Output is correct |
| 4 |
Correct |
104 ms |
30792 KB |
Output is correct |
| 5 |
Correct |
104 ms |
33068 KB |
Output is correct |
| 6 |
Correct |
104 ms |
29520 KB |
Output is correct |
| 7 |
Correct |
233 ms |
30952 KB |
Output is correct |
| 8 |
Correct |
234 ms |
30812 KB |
Output is correct |
| 9 |
Correct |
852 ms |
93008 KB |
Output is correct |
| 10 |
Correct |
570 ms |
86560 KB |
Output is correct |
| 11 |
Correct |
630 ms |
77588 KB |
Output is correct |
| 12 |
Correct |
558 ms |
86412 KB |
Output is correct |
| 13 |
Correct |
375 ms |
63632 KB |
Output is correct |
| 14 |
Correct |
366 ms |
59184 KB |
Output is correct |
| 15 |
Correct |
348 ms |
59104 KB |
Output is correct |
| 16 |
Correct |
330 ms |
59276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
29560 KB |
Output is correct |
| 2 |
Correct |
116 ms |
29204 KB |
Output is correct |
| 3 |
Correct |
108 ms |
29296 KB |
Output is correct |
| 4 |
Correct |
105 ms |
29596 KB |
Output is correct |
| 5 |
Correct |
110 ms |
28520 KB |
Output is correct |
| 6 |
Correct |
131 ms |
29340 KB |
Output is correct |
| 7 |
Correct |
127 ms |
29400 KB |
Output is correct |
| 8 |
Correct |
133 ms |
29684 KB |
Output is correct |
| 9 |
Correct |
148 ms |
29920 KB |
Output is correct |
| 10 |
Correct |
756 ms |
93192 KB |
Output is correct |
| 11 |
Correct |
549 ms |
65500 KB |
Output is correct |
| 12 |
Correct |
460 ms |
67996 KB |
Output is correct |
| 13 |
Correct |
431 ms |
67052 KB |
Output is correct |
| 14 |
Correct |
448 ms |
67936 KB |
Output is correct |
| 15 |
Correct |
295 ms |
57640 KB |
Output is correct |
| 16 |
Correct |
281 ms |
57744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
107 ms |
29560 KB |
Output is correct |
| 2 |
Correct |
116 ms |
29204 KB |
Output is correct |
| 3 |
Correct |
108 ms |
29296 KB |
Output is correct |
| 4 |
Correct |
105 ms |
29596 KB |
Output is correct |
| 5 |
Correct |
110 ms |
28520 KB |
Output is correct |
| 6 |
Correct |
131 ms |
29340 KB |
Output is correct |
| 7 |
Correct |
127 ms |
29400 KB |
Output is correct |
| 8 |
Correct |
133 ms |
29684 KB |
Output is correct |
| 9 |
Correct |
148 ms |
29920 KB |
Output is correct |
| 10 |
Correct |
756 ms |
93192 KB |
Output is correct |
| 11 |
Correct |
549 ms |
65500 KB |
Output is correct |
| 12 |
Correct |
460 ms |
67996 KB |
Output is correct |
| 13 |
Correct |
431 ms |
67052 KB |
Output is correct |
| 14 |
Correct |
448 ms |
67936 KB |
Output is correct |
| 15 |
Correct |
295 ms |
57640 KB |
Output is correct |
| 16 |
Correct |
281 ms |
57744 KB |
Output is correct |
| 17 |
Correct |
590 ms |
67688 KB |
Output is correct |
| 18 |
Correct |
111 ms |
29128 KB |
Output is correct |
| 19 |
Correct |
105 ms |
28816 KB |
Output is correct |
| 20 |
Correct |
118 ms |
29132 KB |
Output is correct |
| 21 |
Correct |
103 ms |
33160 KB |
Output is correct |
| 22 |
Correct |
110 ms |
29172 KB |
Output is correct |
| 23 |
Correct |
173 ms |
30852 KB |
Output is correct |
| 24 |
Correct |
176 ms |
30332 KB |
Output is correct |
| 25 |
Correct |
186 ms |
30432 KB |
Output is correct |
| 26 |
Correct |
177 ms |
30288 KB |
Output is correct |
| 27 |
Correct |
816 ms |
97104 KB |
Output is correct |
| 28 |
Correct |
501 ms |
73620 KB |
Output is correct |
| 29 |
Correct |
508 ms |
74912 KB |
Output is correct |
| 30 |
Correct |
503 ms |
74564 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
936 ms |
94400 KB |
Output is correct |
| 2 |
Correct |
104 ms |
32980 KB |
Output is correct |
| 3 |
Correct |
108 ms |
33216 KB |
Output is correct |
| 4 |
Correct |
107 ms |
33028 KB |
Output is correct |
| 5 |
Correct |
154 ms |
33984 KB |
Output is correct |
| 6 |
Correct |
146 ms |
34432 KB |
Output is correct |
| 7 |
Correct |
169 ms |
30440 KB |
Output is correct |
| 8 |
Correct |
932 ms |
94216 KB |
Output is correct |
| 9 |
Correct |
887 ms |
94648 KB |
Output is correct |
| 10 |
Correct |
845 ms |
94388 KB |
Output is correct |
| 11 |
Correct |
692 ms |
73060 KB |
Output is correct |
| 12 |
Correct |
108 ms |
32768 KB |
Output is correct |
| 13 |
Correct |
103 ms |
29640 KB |
Output is correct |
| 14 |
Correct |
104 ms |
30792 KB |
Output is correct |
| 15 |
Correct |
104 ms |
33068 KB |
Output is correct |
| 16 |
Correct |
104 ms |
29520 KB |
Output is correct |
| 17 |
Correct |
233 ms |
30952 KB |
Output is correct |
| 18 |
Correct |
234 ms |
30812 KB |
Output is correct |
| 19 |
Correct |
852 ms |
93008 KB |
Output is correct |
| 20 |
Correct |
570 ms |
86560 KB |
Output is correct |
| 21 |
Correct |
630 ms |
77588 KB |
Output is correct |
| 22 |
Correct |
558 ms |
86412 KB |
Output is correct |
| 23 |
Correct |
375 ms |
63632 KB |
Output is correct |
| 24 |
Correct |
366 ms |
59184 KB |
Output is correct |
| 25 |
Correct |
348 ms |
59104 KB |
Output is correct |
| 26 |
Correct |
330 ms |
59276 KB |
Output is correct |
| 27 |
Correct |
107 ms |
29560 KB |
Output is correct |
| 28 |
Correct |
116 ms |
29204 KB |
Output is correct |
| 29 |
Correct |
108 ms |
29296 KB |
Output is correct |
| 30 |
Correct |
105 ms |
29596 KB |
Output is correct |
| 31 |
Correct |
110 ms |
28520 KB |
Output is correct |
| 32 |
Correct |
131 ms |
29340 KB |
Output is correct |
| 33 |
Correct |
127 ms |
29400 KB |
Output is correct |
| 34 |
Correct |
133 ms |
29684 KB |
Output is correct |
| 35 |
Correct |
148 ms |
29920 KB |
Output is correct |
| 36 |
Correct |
756 ms |
93192 KB |
Output is correct |
| 37 |
Correct |
549 ms |
65500 KB |
Output is correct |
| 38 |
Correct |
460 ms |
67996 KB |
Output is correct |
| 39 |
Correct |
431 ms |
67052 KB |
Output is correct |
| 40 |
Correct |
448 ms |
67936 KB |
Output is correct |
| 41 |
Correct |
295 ms |
57640 KB |
Output is correct |
| 42 |
Correct |
281 ms |
57744 KB |
Output is correct |
| 43 |
Correct |
590 ms |
67688 KB |
Output is correct |
| 44 |
Correct |
111 ms |
29128 KB |
Output is correct |
| 45 |
Correct |
105 ms |
28816 KB |
Output is correct |
| 46 |
Correct |
118 ms |
29132 KB |
Output is correct |
| 47 |
Correct |
103 ms |
33160 KB |
Output is correct |
| 48 |
Correct |
110 ms |
29172 KB |
Output is correct |
| 49 |
Correct |
173 ms |
30852 KB |
Output is correct |
| 50 |
Correct |
176 ms |
30332 KB |
Output is correct |
| 51 |
Correct |
186 ms |
30432 KB |
Output is correct |
| 52 |
Correct |
177 ms |
30288 KB |
Output is correct |
| 53 |
Correct |
816 ms |
97104 KB |
Output is correct |
| 54 |
Correct |
501 ms |
73620 KB |
Output is correct |
| 55 |
Correct |
508 ms |
74912 KB |
Output is correct |
| 56 |
Correct |
503 ms |
74564 KB |
Output is correct |
| 57 |
Correct |
530 ms |
72584 KB |
Output is correct |
| 58 |
Correct |
874 ms |
92956 KB |
Output is correct |
| 59 |
Correct |
639 ms |
76976 KB |
Output is correct |
