Submission #515858

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
515858	2022-01-20T02:19:48 Z	gumbymoo	Monkey and Apple-trees (IZhO12_apple)	Java 11	100 / 100	1362 ms	205888 KB

apple

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class apple {
	
	static class Query {
		
		public int type, a, b;
		public long x;
		
		public Query(int type, int a, int b) {
			this.type = type; this.a = a; this.b = b;
		}
		
		public Query(int type, int a, int b, long x) {
			this.type = type; this.a = a; this.b = b; this.x = x;
		}
		
	}
	
	static Node root;
	static int maxN = 1000000001;
	
	static class Node {
		
		long val = 0;
		long lzSet = 0;
		
		Node left, right;
		
		public Node getLeft() {
			if(left == null)
				left = new Node();
			return left;
		}
		
		public Node getRight() {
			if(right == null)
				right = new Node();
			return right;
		}
		
	}
	
	//static Node[] segtree;
	static long[] t;
	static int n;
	
	static void pullup(Node v) {
		v.val = v.getLeft().val + v.getRight().val;
	}
	
	static void pushdown(Node v, int l, int r) {
		
		if(l == r)
			return;
		
		int mid = (l+r)/2;
		
		if(v.lzSet != 0) {
			v.getLeft().lzSet = v.getRight().lzSet = v.lzSet;
			v.getLeft().val = (mid - l + 1) * v.lzSet;
			v.getRight().val = (r - mid) * v.lzSet;
			v.lzSet = 0;
		}
	}
	
	/*
	static void build(Node v, int l, int r) {
		if(l == r) {
			v.val = t[l]; return;
		}
		int mid = (l+r)>>1;
		build(2*v,l,mid);
		build(2*v+1,mid+1,r);
		pullup(v);
	}
	*/
	
	//static void build() { build(1,0,n-1); }
	
	/*
	static void add(Node v, int l, int r, int cl, int cr, long val) {
		if(cr < l || cl > r) return;
		if(l <= cl && cr <= r) {
			v.val += (cr - cl + 1) * val;
			if(v.lzSet == 0) v.lzAdd += val;
			else v.lzSet += val;
			return;
		}
		int mid = (cl+cr)>>1;
		pushdown(v, cl, cr);
		add(v.getLeft(), l, r, cl, mid, val);
		add(v.getRight(), l, r, mid+1, cr, val);
		pullup(v);
	}
	*/
	
	//static void add(int l, int r, long val) { add(root,l,r,1,maxN,val); }
	
	static void set(Node v, int l, int r, int cl, int cr, long val) {
		if(cr < l || cl > r) return;
		if(l <= cl && cr <= r) {
			v.val = (cr - cl + 1) * val;
			//v.lzAdd = 0;
			v.lzSet = val;
			return;
		}
		int mid = (cl+cr)>>1;
		pushdown(v,cl,cr);
		set(v.getLeft(),l,r,cl,mid,val);
		set(v.getRight(),l,r,mid+1,cr,val);
		pullup(v);
	}
	
	static void set(int l, int r, long val) { set(root,l,r,1,maxN,val); }
	
	static long query(Node v, int l, int r, int cl, int cr) {
		if(cr < l || cl > r) return 0;
		if(cr <= r && cl >= l) return v.val;
		int mid = (cl+cr)>>1;
		pushdown(v,cl,cr);
		return query(v.getLeft(),l,r,cl,mid) + query(v.getRight(),l,r,mid+1,cr);
	}
	
	static long query(int l, int r) { return query(root,l,r,1,maxN); }
	
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		//BufferedReader br = new BufferedReader(new FileReader("f.in"));
		//PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("f.out")));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		//n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		
		/*
		t = new long[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < n; i++)
			t[i] = Integer.parseInt(st.nextToken());
			*/
		
		ArrayList<Query> queries = new ArrayList<Query>();
		
		for(int i = 0; i < q; i++) {
			st = new StringTokenizer(br.readLine());
			int type = Integer.parseInt(st.nextToken());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			queries.add(new Query(type, a, b));
		}
		
		//long initTime = System.currentTimeMillis();
		
		root = new Node();
		
		long c = 0;
		
		for(Query query : queries) {
			switch(query.type) {
			case 1:
				c = query((int) (query.a+c), (int) (query.b+c));
				pw.println(c);
				break;
			case 2:
				set((int) (query.a+c), (int) (query.b+c),1);
				break;
			}
		}
		
		//pw.println("RUNTIME: " + (System.currentTimeMillis() - initTime));
		pw.close();
		
	}

}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	60 ms	8352 KB	Output is correct
2	Correct	61 ms	8256 KB	Output is correct
3	Correct	67 ms	8260 KB	Output is correct
4	Correct	348 ms	18080 KB	Output is correct
5	Correct	369 ms	17584 KB	Output is correct
6	Correct	366 ms	17836 KB	Output is correct
7	Correct	365 ms	17668 KB	Output is correct
8	Correct	681 ms	55452 KB	Output is correct
9	Correct	825 ms	88216 KB	Output is correct
10	Correct	849 ms	88308 KB	Output is correct
11	Correct	1066 ms	112416 KB	Output is correct
12	Correct	1064 ms	112252 KB	Output is correct
13	Correct	1131 ms	126692 KB	Output is correct
14	Correct	1098 ms	124888 KB	Output is correct
15	Correct	1321 ms	205888 KB	Output is correct
16	Correct	1362 ms	203084 KB	Output is correct
17	Correct	1068 ms	124948 KB	Output is correct
18	Correct	1110 ms	126244 KB	Output is correct
19	Correct	1290 ms	200904 KB	Output is correct
20	Correct	1312 ms	201180 KB	Output is correct