Submission #515857

#	Time	Username	Problem	Language	Result	Execution time	Memory
515857		gumbymoo	Monkey and Apple-trees (IZhO12_apple)	Java	0 / 100	1432 ms	262148 KiB

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, lzAdd = 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.getLeft().lzAdd = v.getRight().lzAdd = v.lzSet = 0;
		} else if(v.lzAdd != 0) {
			if(v.getLeft().lzSet == 0) {
				v.getLeft().lzAdd += v.lzAdd;
			} else {
				v.getLeft().lzSet += v.lzAdd;
				v.getLeft().lzAdd = 0;
			}
			if(v.getRight().lzSet == 0) {
				v.getRight().lzAdd += v.lzAdd;
			} else {
				v.getRight().lzSet += v.lzAdd;
				v.getRight().lzAdd = 0;
			}
			v.getLeft().val += (mid - l + 1) * v.lzAdd;
			v.getRight().val += (r - mid) * v.lzAdd;
			v.lzAdd = 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: 0 / 100