답안 #525588

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525588	2022-02-12T04:26:30 Z	shmad	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	418 ms	262148 KB

apple

#pragma GCC optimize("O3", "unroll-loops") // "Ofast"
#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt") 

#include <bits/stdc++.h>

#define int long long
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define dbg(x) cerr << #x << " = " << x << '\n'

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vvi = vt< vt<int> >;

const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 60);
const double eps = 1e-6;

int n;

struct Node {
	int sum, tag;
	Node *l, *r;
	Node () : sum(0), tag(0), l(nullptr), r(nullptr) {}
	Node (Node *x, Node *y) : l(x), r(y), sum(0), tag(0) { sum += (x ? x -> sum : 0) + (y ? y -> sum : 0); }
}*root;                              

void f (Node* &v) {
	if (!v) v = new Node();	
}

void push (Node* &v, int tl, int tr) {
	f(v -> l);
	f(v -> r);
	if (v -> tag) {
		v -> sum = (tr - tl + 1) * v -> tag;
		if (tl != tr) {
			v -> l -> tag = v -> tag;
			v -> r -> tag = v -> tag;
		}
	}
	v -> tag = 0;
}

void upd (Node *v, int l, int r, int val, int tl = 1, int tr = mod) {
	if (!v) return;
	push(v, tl, tr);
	if (tl > r || tr < l) return;
	if (tl >= l && tr <= r) {
	    v -> tag = val;
		push(v, tl, tr);
		return;
	}
	f(v -> l);
	f(v -> r);
	int tm = tl + tr >> 1;
	upd(v -> l, l, r, val, tl, tm);
	upd(v -> r, l, r, val, tm + 1, tr);
	v -> sum = (v -> l -> sum) + (v -> r -> sum);
}

int get (Node *v, int l, int r, int tl = 1, int tr = mod) {
	if (!v) return 0;
	push(v, tl, tr);
	if (tl > r || tr < l) return 0;
	if (tl >= l && tr <= r) return v -> sum;
	int tm = tl + tr >> 1;
	int a = 0;
	if (v -> l) a = get(v -> l, l, r, tl, tm);
	int b = 0;
	if (v -> r) b = get(v -> r, l, r, tm + 1, tr);
	return a + b;
}

void solve () {
	cin >> n;
	root = new Node();
	int c = 0;
	for (int i = 1; i <= n; i++) {
		int tp, x, y;
		cin >> tp >> x >> y;
		if (tp == 1) {
			c = get(root, x + c, y + c);
			cout << c << '\n';
		}
		if (tp == 2) upd(root, x + c, y + c, 1);
	}
	cout << '\n';	
}                                              

bool testcases = 0;

signed main() {
#ifdef ONLINE_JUDGE
	freopen(".in", "r", stdin);
	freopen(".out", "w", stdout);
#endif
    cin.tie(0) -> sync_with_stdio(0);
    int test = 1;
    if (testcases) cin >> test;
    for (int cs = 1; cs <= test; cs++) {
        solve();
    }
}

Compilation message

apple.cpp: In constructor 'Node::Node(Node*, Node*)':
apple.cpp:27:12: warning: 'Node::r' will be initialized after [-Wreorder]
   27 |  Node *l, *r;
      |            ^
apple.cpp:26:6: warning:   'long long int Node::sum' [-Wreorder]
   26 |  int sum, tag;
      |      ^~~
apple.cpp:29:2: warning:   when initialized here [-Wreorder]
   29 |  Node (Node *x, Node *y) : l(x), r(y), sum(0), tag(0) { sum += (x ? x -> sum : 0) + (y ? y -> sum : 0); }
      |  ^~~~
apple.cpp: In function 'void upd(Node*, long long int, long long int, long long int, long long int, long long int)':
apple.cpp:60:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |  int tm = tl + tr >> 1;
      |           ~~~^~~~
apple.cpp: In function 'long long int get(Node*, long long int, long long int, long long int, long long int)':
apple.cpp:71:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |  int tm = tl + tr >> 1;
      |           ~~~^~~~

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	19 ms	9408 KB	Output is correct
5	Correct	21 ms	11328 KB	Output is correct
6	Correct	22 ms	10916 KB	Output is correct
7	Correct	22 ms	11308 KB	Output is correct
8	Correct	191 ms	86828 KB	Output is correct
9	Correct	370 ms	150316 KB	Output is correct
10	Correct	383 ms	166544 KB	Output is correct
11	Correct	418 ms	179080 KB	Output is correct
12	Correct	414 ms	184716 KB	Output is correct
13	Correct	370 ms	215216 KB	Output is correct
14	Correct	375 ms	217128 KB	Output is correct
15	Runtime error	383 ms	262148 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-