Submission #735296

# Submission time Handle Problem Language Result Execution time Memory
735296 2023-05-03T22:03:18 Z CutSandstone Examination (JOI19_examination) Java 11
2 / 100
3000 ms 454896 KB
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class examination {
	// change to ur file
	private static final String localTestInputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.in";
	private static final String localTestOutputFile = "C:\\Users\\anaba\\eclipse-workspace\\test\\src\\main\\java\\input.out";
	// for usaco only
	private static final String name = "mincross";
	// 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;
	// all are primes
	private static final long mod1 = 4611686018427387847L, mod2 = 4611686018427387833L, mod3 = 4611686018427387813L;
	// 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(localTestInputFile).exists()){
				sc = new FastIO(localTestInputFile);
				out = new PrintWriter(new BufferedOutputStream(System.out));
//				out = new PrintWriter(localTestOutputFile);
				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 N = sc.nextInt(), Q = sc.nextInt();
		int[][] nums = new int[N][2];
		for(int[] a: nums) {a[0] = sc.nextInt(); a[1] = sc.nextInt();}
		Arrays.sort(nums, (a, b) -> b[0]+b[1]-a[0]-a[1]);
		int[][] q = new int[Q][4];
		int[] ans = new int[Q];
		for(int i = 0; i<Q; i++) {
			q[i][0] = sc.nextInt();
			q[i][1] = sc.nextInt();
			q[i][2] = sc.nextInt();
			q[i][3] = i;
		}
		Arrays.sort(q, (a, b) -> b[2]-a[2]);
		ST2D st = new ST2D(mod-6);
		int p = 0;
		for(int[] a: q) {
			while(p < N && nums[p][0]+nums[p][1] >= a[2]) st.add(nums[p][0], nums[p++][1], 1);
			ans[a[3]] = (int)st.sum(a[0], a[1], mod-7, mod-7);
		}
		outLn(ans);
	}
	// 2d segtree sparse point add range sum
	private static class ST2D{
		private ST2D left, right;
		private AST<Long> st;
		private final long l, r, N;
		public ST2D(long N) {this(0, N-1, N);}
		private ST2D(long l, long r, long N) {
			st = new AST<>(N, (a, b) -> a+b, (len) -> 0L);
			this.l = l;
			this.r = r;
			this.N = N;
		}
		public void add(long x, long y, long num) {
			if(l != r) {
				long mid = (l+r)>>1;
				if(left == null) {
					left = new ST2D(l, mid, N);
					right = new ST2D(mid+1, r, N);
				}
				if(x <= mid) left.add(x, y, num);
				else right.add(x, y, num);
			}
			st.set(y, num+st.get(y));
		}
		public long sum(long x1, long y1, long x2, long y2) {
			if(x1 == l && x2 == r) return st.get(y1, y2);
			long mid = (l+r)>>1;
			if(left == null) {
				left = new ST2D(l, mid, N);
				right = new ST2D(mid+1, r, N);
			}
			if(x2 <= mid) return left.sum(x1, y1, x2, y2);
			if(x1 > mid) return right.sum(x1, y1, x2, y2);
			return left.sum(x1, y1, mid, y2)+right.sum(mid+1, y1, x2, y2);
		}
	}
	// 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> {
    	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> {public Object get(Edit a);}
    	private final T[] nums;
    	private final int block;
    	private final List<int[]> quer;
    	private final Add<Edit, T> add;
    	private final Rem<Edit, T> rem;
    	private final Get<Edit> get;
    	private Edit def;
    	public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit> get, Edit def) {
    		this(nums, add, rem, get, def, -1);
    	}
    	public MoAlg(T[] nums, Add<Edit, T> add, Rem<Edit, T> rem, Get<Edit> 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.add(new int[] {l, r, quer.size()});
    	}
    	public Object[] getAns() {
    		Collections.sort(quer, (a, b) -> a[0]/block == b[0]/block ? ((((a[0]/block)&1) == 0) ? a[1]-b[1]:b[1]-a[1]):a[0]-b[0]);
    		int l = 0, r = -1;
    		Object[] ans = new Object[quer.size()];
    		for(int[] a: quer) {
    			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);
    		}
    		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 len);}
	public interface LZ<Lz>{Lz oper(Lz top, Lz current);}
	public interface Def<Val>{Val get(long len);}
	public interface DefLz<Lz>{Lz get();}
	// convex hull trick
    private static class CHT {
	    private List<Line> lines;
	    private boolean max;
	    
	    public CHT(boolean max) {
	        this.lines = new ArrayList<>();
	        this.max = max;
	    }
	    public boolean isEmpty() {return lines.isEmpty();}
	    public void add(long m, long b) {
	    	if(max) {
	    		m*=-1;
	    		b*=-1;
	    	}
	        Line line = new Line(m, b);
	        while (lines.size() >= 2) {
	            Line l1 = lines.get(lines.size() - 1);
	            Line l2 = lines.get(lines.size() - 2);
	            if (BigInteger.valueOf(l1.b-l2.b).multiply(BigInteger.valueOf(l1.m-line.m))
	            		.compareTo(BigInteger.valueOf(line.b-l1.b).multiply(BigInteger.valueOf(l2.m-l1.m))) == 1)
	                lines.remove(lines.size() - 1);
	            else break;
	        }
	        lines.add(line);
	    }
 
	    public long get(long x) {
	        int lo = 0, hi = lines.size() - 1;
	        while (lo < hi) {
	            int mid = (lo + hi) / 2;
	            if (lines.get(mid).yValue(x) < lines.get(mid + 1).yValue(x))
	                hi = mid;
	            else lo = mid + 1;
	        }
	        return (max ? -1:1)*lines.get(lo).yValue(x);
	    }
 
	    private static class Line {
	        private long m;
	        private long b;
 
	        public Line(long m, long b) {
	            this.m = m;
	            this.b = b;
	        }
 
	        public long yValue(long x) {
	            return m * x + b;
	        }
	    }
	}
    // convex hull
    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;
	}
	// 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(0, len-1, add);}
		
		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();
		}
	}
	// all the binary jumping/lifting stuff, Range stores the memory of each range
	// Range combine is <lower, higher>
	private static class Lift<Range> {
		private final int[][] up;
		private final int[] depth;
		private int lg;
		private final Comb<Range> comb;
		private final Range[][] upMem;
		public Lift(int N, List<Two<Integer, Range>>[] g, Comb<Range> comb) {
			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);
			dfs(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 dfs(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;
				dfs(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 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;
		}
	}
	// 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<>();
		LinkedList<List<Integer>> ans = new LinkedList<>();
		ans.add(new LinkedList<>());
		for (int i = 0; i<N; i++)
			if (disc[i] == -1)
				SCCUtil(i, low, disc, stackMember, st, 0, g, ans);
		ans.pollLast();
		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 LinkedList<>());
		}
		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;
	}
	// counts amount of numbers using treemap
	private static class Cnt<T> {
		
		public TreeMap<T, Long> map;
		boolean first = true;
		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;
			}
			Long get = map.get(num);
			if (get == null)
				return 0;
			return get;
		}
		
		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) {
			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 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("2147483647", "inf"));
	}
	private static void out(int[] a) {
		for(int i: a) out.print(i+" ");
		out.println();
	}
	private static void out(long[] a) {
		for(long l: a) out.print(l+" ");
		out.println();
	}
	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);
	}
	// basic math
	private static long gcd(long... arr) {
		long ans = arr[0];
		for(int i = 1; i<arr.length; i++) {
			while(arr[i] > 0) {
				long t = ans%arr[i];
				ans = arr[i];
				arr[i] = t;
			}
		}
		return ans;
	}
	private static int max(int... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.max(x[0], x[i]);
		return x[0];
	}
	private static int min(int... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.min(x[0], x[i]);
		return x[0];
	}
	private static long max(long... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.max(x[0], x[i]);
		return x[0];
	}
	private static long min(long... x) {
		for (int i = 1; i < x.length; i++)
			x[0] = Math.min(x[0], x[i]);
		return x[0];
	}
	// modular arithmatic
	private static class Mod {
		static long mod = (int)(1e9+7);
		private Mod() {
			
		}
		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 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);
		}
		
		private BS() {
			
		}
		
		public static long last(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 long first(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;
		}
	}
	// 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;
		}
	}
	//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, Def<Val[]> def) {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)];
		}
	}
	// 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.toString() + ", " + b.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(r-l+1);
			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, r-l+1);
		}
	}
    // 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(r-l+1);
			}
		}
		private final Comb<Val> oper;
		private final Node<Val> top;
		private final Def<Val> def;
		public AST(long n, Comb<Val> oper) {this(n, oper, (a) -> 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) {
			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) {
			Node<Val> t = top;
			while(t.l != t.r) {
				if(t.le == null) return def.get(1);
				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);
			return get(a, b, top);
		}
		private Val get(long a, long b, Node<Val> n) {
			if(n == null) return def.get(b-a+1);
			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);
		}
	}
	// 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();
		}
	}
	// 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 int def;
		
		public ST(int n, Oper oper, int 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 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 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[500007];
		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[] 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: examination.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# Verdict Execution time Memory Grader output
1 Correct 86 ms 10776 KB Output is correct
2 Correct 96 ms 10704 KB Output is correct
3 Correct 103 ms 10552 KB Output is correct
4 Correct 105 ms 13012 KB Output is correct
5 Correct 94 ms 13076 KB Output is correct
6 Correct 97 ms 12948 KB Output is correct
7 Correct 2281 ms 382944 KB Output is correct
8 Correct 2298 ms 382964 KB Output is correct
9 Correct 2221 ms 382872 KB Output is correct
10 Correct 1773 ms 215464 KB Output is correct
11 Correct 1501 ms 215332 KB Output is correct
12 Correct 390 ms 15120 KB Output is correct
13 Correct 1737 ms 381852 KB Output is correct
14 Correct 1711 ms 381864 KB Output is correct
15 Correct 1793 ms 381848 KB Output is correct
16 Correct 1141 ms 208308 KB Output is correct
17 Correct 1575 ms 216996 KB Output is correct
18 Correct 250 ms 14776 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 454896 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 3084 ms 454896 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 86 ms 10776 KB Output is correct
2 Correct 96 ms 10704 KB Output is correct
3 Correct 103 ms 10552 KB Output is correct
4 Correct 105 ms 13012 KB Output is correct
5 Correct 94 ms 13076 KB Output is correct
6 Correct 97 ms 12948 KB Output is correct
7 Correct 2281 ms 382944 KB Output is correct
8 Correct 2298 ms 382964 KB Output is correct
9 Correct 2221 ms 382872 KB Output is correct
10 Correct 1773 ms 215464 KB Output is correct
11 Correct 1501 ms 215332 KB Output is correct
12 Correct 390 ms 15120 KB Output is correct
13 Correct 1737 ms 381852 KB Output is correct
14 Correct 1711 ms 381864 KB Output is correct
15 Correct 1793 ms 381848 KB Output is correct
16 Correct 1141 ms 208308 KB Output is correct
17 Correct 1575 ms 216996 KB Output is correct
18 Correct 250 ms 14776 KB Output is correct
19 Execution timed out 3084 ms 454896 KB Time limit exceeded
20 Halted 0 ms 0 KB -