Submission #879672

# Submission time Handle Problem Language Result Execution time Memory
879672 2023-11-27T22:06:44 Z rlubiniecki Monkey and Apple-trees (IZhO12_apple) Java 11
0 / 100
313 ms 71808 KB
import java.io.*;
import java.util.*;
public class apple {

	public static void main(String args[]) throws Exception {
		IOStream io = new IOStream();
		int q = io.nextInt();
		SegTree tree = new SegTree();
		int c = 0;
		while(q-->0) {
			int d = io.nextInt();
			int x = io.nextInt()-1+c;
			int y = io.nextInt()-1+c;
			if(d==2) {
				tree.set(x, y, 1);
			}
			else {
				c = tree.sum(x, y);
				io.println(c);
			}
		}
		io.close();
	}
	static class SegTree {
		Node[] tree;
		int upper = (1<<30)-1;
		int count = 1;
		public SegTree() {
			tree = new Node[1000000];
			for(int i=0;i<tree.length;i++) tree[i] = new Node();
			tree[0].lx = 0;
			tree[0].rx = upper;
		}
		public void propogate(int node) {
			int len = tree[node].rx-tree[node].lx+1;
			if(len==1) {
				if(tree[node].lazy!=-1) tree[node].sum = tree[node].lazy;
				tree[node].lazy = -1;
			}
			if(tree[node].l==-1) {
				int m = (tree[node].lx+tree[node].rx)/2;
				tree[node].l = count++;
				tree[node].r = count++;
				tree[tree[node].l].setBounds(tree[node].lx, m);
				tree[tree[node].r].setBounds(m+1, tree[node].rx);
			}
			if(tree[node].lazy!=-1) {
				tree[node].sum = tree[node].lazy*len;
				tree[tree[node].l].lazy = tree[node].lazy;
				tree[tree[node].r].lazy = tree[node].lazy;
				tree[node].lazy = -1;
			}
		}
		public int set(int l, int r, int node, int val) {
			propogate(node);
			if(tree[node].lx>r || tree[node].rx<l) return tree[node].sum;
			if(tree[node].lx>=l && tree[node].rx<=r) {
				tree[node].lazy = val;
				return 0;
			}
			int overlap = Math.min(r, tree[node].rx)-Math.max(l, tree[node].lx)+1;
			int unused = set(l,r,tree[node].l,val)+set(l,r,tree[node].r,val);
			tree[node].sum = unused+overlap*val;
			return unused;
		}
		public int sum(int l, int r, int node) {
			propogate(node);
			if(tree[node].lx>r || tree[node].rx<l) return 0;
			if(tree[node].lx>=l && tree[node].rx<=r) return tree[node].sum;
			return sum(l,r,tree[node].l)+sum(l,r,tree[node].r);
		}
		public int set(int l, int r, int val) {
			return set(l,r,0,val);
		}
		public int sum(int l, int r) {
			return sum(l,r,0);
		}
	}
	static class Node {
		int l, r, sum, lazy, lx, rx;
		public Node() {
			l = -1;
			r = -1;
			sum = 0;
			lazy = -1;
			lx = 3000;
			rx = 3000;
		}
		public void setBounds(int l, int r) {
			this.lx = l;
			this.rx = r;
		}
	}
	static class IOStream extends PrintWriter {
		final private int BUFFER_SIZE = 1 << 16;
		private DataInputStream din;
		private byte[] buffer;
		private int bufferPointer, bytesRead;

		public IOStream() {
			super(System.out);
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public IOStream(String input, String output) throws IOException {
			super(output);
			din = new DataInputStream(new FileInputStream(input));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64]; // line length
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n') {
					if (cnt != 0) {
						break;
					} else {
						continue;
					}
				}
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}

		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ') {
				c = read();
			}
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}

		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}

		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}
			if (neg)
				return -ret;
			return ret;
		}

		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}

		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() {
			if (din == null)
				return;
			try {
				din.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
			super.close();
		}
	}

}
# Verdict Execution time Memory Grader output
1 Correct 129 ms 66224 KB Output is correct
2 Correct 142 ms 64464 KB Output is correct
3 Correct 127 ms 64368 KB Output is correct
4 Correct 230 ms 69660 KB Output is correct
5 Correct 240 ms 70260 KB Output is correct
6 Correct 235 ms 69924 KB Output is correct
7 Correct 255 ms 67760 KB Output is correct
8 Runtime error 313 ms 71808 KB Execution failed because the return code was nonzero
9 Halted 0 ms 0 KB -