제출 #385393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385393		randomjohnnyh	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	733 ms	207820 KiB

apple

/*
TASK:
LANG: C++11
*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <list>
#include <vector>
#include <map>
#include <sstream>
#include <cmath>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cassert>
#include <deque>
#include <tuple>
#include <functional>
#include <iomanip>
 
using namespace std;
 
//#define GEN
#define LOCAL
 
const double Pi = acos(-1.0);
 
typedef long long ll;
 
typedef pair<int, int> pii;
typedef pair <ll, ll> pll;
 
#define Set(a, s) memset(a, s, sizeof (a))
 
#define Rd(r) ifstream cin(r)
#define Wt(w) ofstream cout(w)
#define SIO(f) Rd(((string)f+".in").c_str());Wt(((string)f+".out").c_str())
#define FASTIO ios::sync_with_stdio(0);cin.tie(0)
 
const int inf = 1000000007;
const ll llinf = 800000000000000119;
 
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
//const int dx[8] = { 1, 1, 1, 0, 0, -1, -1, -1}, dy[8] = { 1, 0, -1, 1, -1, 1, 0, -1};
 
//to_string
string to_string(string s) {
#ifdef LOCAL
	return '"' + s + '"';
#endif // LOCAL
	return s;
}
string to_string(const char* s) {
	return to_string((string)s);
}
string to_string(bool b) {
#ifdef LOCAL
	return (b ? "true" : "false");
#endif // LOCAL
	return to_string((int)b);
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto& x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}
#define N 4
template <typename T>
string to_string(T* v) {
	bool first = true;
	string res = "{";
	for (int i = 0; i < N; i++) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(*v);
		v++;
	}
	res += "}";
	return res;
}
 
//dprintf
 
void debug_out() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
 
#ifdef LOCAL
#define dprintf(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define dprintf(...) 41
#endif
 
//vector output
 
template <class T>
ostream& operator<<(ostream& stream, vector <T> v) {
	for (T i : v) {
		stream << i << " ";
	}
#ifdef LOCAL
	stream << "\b";
#endif
	return stream;
}
 
// cross product
 
int cross(int a1, int b1, int a2, int b2) { return (a1 * b2 - a2 * b1); }
int ccw(pii a, pii b, pii c) { return cross(b.first - a.first, b.second - a.second, c.first - a.first, c.second - a.second); }
 
//hi
 
void hi() { printf("hi\n"); }
void hi(string flag) { dprintf("hi (%s)\n", flag.c_str()); }
 
#ifndef SEGTREE_I_INCLUDED
#define SEGTREE_I_INCLUDED
 
struct segtree_node {
	segtree_node* left_child, * right_child;
	int left_bound, right_bound;
	int sum;
	int lazy;
 
	void update_node(int val) {
		sum = (right_bound - left_bound + 1) * val;
		lazy = val;
		// cout << "update_node " << left_bound << " " << right_bound << " " << sum << " " << lazy << endl;
	}
	void merge() {
		sum = 0;
		if (left_child != NULL) {
			sum += left_child->sum;
		}
		if (right_child != NULL) {
			sum += right_child->sum;
		}
	}
	void prop() {
		if (lazy == -1) return;
		int mid = left_bound + (right_bound - left_bound) / 2;
		if (left_child == NULL) left_child = new segtree_node(left_bound, mid);
		left_child->update_node(lazy);
		if (right_child == NULL) right_child = new segtree_node(mid + 1, right_bound);
		right_child->update_node(lazy);
		lazy = -1;
	}
 
	void update(int left, int right, int val) {
		// cout << "update " << left_bound << " " << right_bound << " " << left << " " << right << " " << val << endl;
		if (left_bound >= left && right_bound <= right) {
			update_node(val);
			return;
		}
		prop();
		int mid = left_bound + (right_bound - left_bound) / 2;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			left_child->update(left, right, val);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			right_child->update(left, right, val);
		}
		merge();
	}
	int query(int left, int right) {
		if (left_bound >= left && right_bound <= right) {
			return sum;
		}
		prop();
		int mid = left_bound + (right_bound - left_bound) / 2;
		int res = 0;
		if (left <= mid) {
			if (left_child == NULL) {
				left_child = new segtree_node(left_bound, mid);
			}
			res += left_child->query(left, right);
		}
		if (right > mid) {
			if (right_child == NULL) {
				right_child = new segtree_node(mid + 1, right_bound);
			}
			res += right_child->query(left, right);
		}
		return res;
	}
 
	segtree_node() {
		left_child = right_child = NULL;
		left_bound = right_bound = -1;
		sum = 0; lazy = -1;
	}
	segtree_node(int left, int right) {
		left_child = right_child = NULL;
		left_bound = left; right_bound = right;
		sum = 0; lazy = -1;
	}
};
#endif
 
int main() {
	segtree_node* segtree = new segtree_node(0, inf);
	int c = 0;
 
	int m;
	cin >> m;
	for (int i = 0; i < m; i++) {
		int d, x, y;
		cin >> d >> x >> y;
		if (d == 1) {
			c = segtree->query(x + c, y + c);
			cout << c << endl;
		} else {
			// cout << "updating " << endl;
			segtree->update(x + c, y + c, 1);
		}
		// cout << c << endl;
		// for (int a = 0; a <= 10; a++) {
		// 	cout << segtree->query(a, a) << " ";
		// }
		// cout << endl;
	}
	return 0;
}
 

• Subtask 1: 100 / 100