답안 #515857

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515857	2022-01-20T02:16:26 Z	gumbymoo	원숭이와 사과 나무 (IZhO12_apple)	Java 11	0 / 100	1432 ms	262148 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, 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.0

#	결과	실행 시간	메모리	Grader output
1	Correct	64 ms	8276 KB	Output is correct
2	Correct	60 ms	8308 KB	Output is correct
3	Correct	63 ms	8500 KB	Output is correct
4	Correct	385 ms	19028 KB	Output is correct
5	Correct	409 ms	20460 KB	Output is correct
6	Correct	393 ms	20840 KB	Output is correct
7	Correct	447 ms	20368 KB	Output is correct
8	Correct	755 ms	59672 KB	Output is correct
9	Correct	1087 ms	114984 KB	Output is correct
10	Correct	1070 ms	114656 KB	Output is correct
11	Correct	1115 ms	113616 KB	Output is correct
12	Correct	1073 ms	112964 KB	Output is correct
13	Correct	1055 ms	128828 KB	Output is correct
14	Correct	1090 ms	128372 KB	Output is correct
15	Runtime error	1432 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-