답안 #1078488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1078488	2024-08-27T18:21:45 Z	brun0matheus	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	28 ms	3164 KB

apple

// https://oj.uz/problem/view/IZhO12_apple
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pii> vpi;

const ll maxn = 2e5 + 10;
const ll inf = LLONG_MAX;

#define pb push_back
#define ppb pop_back 
#define ff first
#define ss second 
#define sza(x) ((int)(x).size())
#define all(a) (a).begin(), (a).end()
#define smax(s, v) s = max(s, (v))
#define smin(s, v) s = min(s, (v))

#define FF(i, n) for(int i = 0; i < (n); i++)
#define FF1(i, n) for(int i = 1; i <= (n); i++)
#define FFZ(i, v) FF(i, sza(v))
#define FFS(i, s, n) for(int i = s; i <= (n); i++)
#define FFD(i, n) for(int i = (n)-1; i >= 0; i--)

#define F(n) FF(i, n)
#define F1(n) FF1(i, n)
#define FZ(v) FFZ(i, v)
#define FS(s, n) FFS(i, s, n)
#define FD(n) FFD(i, n)

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << "(" << p.ff << ", " << p.ss << ")"; }
template<typename A> ostream& operator<<(ostream& os, const vector<A>& v) { os << "["; for(const auto& x: v) os << x << ", "; return os << "]"; }

//#define LOCAL
#ifdef LOCAL
void dbg_out() { cerr << endl; }
template<typename H, typename... T> void dbg_out(H h, T... t) { cerr << " " << h; dbg_out(t...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif

ll n, m, p, q, k;
ll a[maxn];

// 1 indexado
// Note que EL, ER mudaram um pouco

#define EL l, (l + r) / 2
#define ER (l + r) / 2 + 1, r
#define INI &seg.root, 1, n

struct Node {
    ll v;
	bool full;
    Node *l, *r;

    Node(ll v = 0) : v(v), l(0), r(0), full(0) {}
	void merge(Node l, Node r) {
		v = l.v + r.v;
		full = l.full && r.full;
	}
	void merge() { merge(*l, *r); }
	void update(ll l, ll r) {
		v = r - l + 1;
		full = 1;
	}
};

struct Seg {
	Node root;

	// Cuidado se for fazer lazy, tem que verificar se nao eh folha antes
	inline void extend(Node *v) {
		if(v->l == 0) {
			v->l = new Node();
			v->r = new Node();
		}
	}

	void update(ll ql, ll qr, Node *v, ll l, ll r) {
		dbg("Upd in", v->v, v->full, l, r);
		if(v->full || l > qr || r < ql) { dbg("Nao mudou", l, r); return;}
		if(ql <= l && r <= qr) {			
			v->update(l, r);
			dbg("Cheio", l, r, v->v, v->full);
			return;
		}
		
		extend(v);
		update(ql, qr, v->l, EL); update(ql, qr, v->r, ER);
		v->merge();
		dbg("Merge", l, r, v->v, v->full);
	}

    Node query(int ql, int qr, Node *v, int l, int r) {
		dbg("Query in", v->v, v->full, l, r);
		
        if(l > qr || r < ql) { dbg("Zero", l, r); return Node(); }
        if(ql <= l && r <= qr) { dbg("Proprio", l, r, v->v, v->full); return *v; }
		if(v->full) {
			Node res = Node( min(r, qr) - max(l, ql) + 1 );
			dbg("Inter", l, r, res.v, res.full);
			return res;
		}

		extend(v);
		
		Node res;
		res.merge(query(ql, qr, v->l, EL), query(ql, qr, v->r, ER));
		dbg("Merge", l, r, res.v, res.full);
        return res;
    }
};

Seg seg;

void solve() {
    cin >> m;
	n = 1 << 30;

	ll c = 0;
	
    F(m) {
		ll d, a, b;
		cin >> d >> a >> b;

		a += c;
		b += c;
		
		if(d == 1) {
			ll tmp = seg.query(a, b, INI).v;
			c = tmp;
			cout << tmp << '\n';
		} else {
			seg.update(a, b, INI);
		}
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

solve();
}

Compilation message

apple.cpp: In constructor 'Node::Node(ll)':
apple.cpp:61:15: warning: 'Node::r' will be initialized after [-Wreorder]
   61 |     Node *l, *r;
      |               ^
apple.cpp:60:7: warning:   'bool Node::full' [-Wreorder]
   60 |  bool full;
      |       ^~~~
apple.cpp:63:5: warning:   when initialized here [-Wreorder]
   63 |     Node(ll v = 0) : v(v), l(0), r(0), full(0) {}
      |     ^~~~

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	460 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	3 ms	608 KB	Output is correct
5	Correct	3 ms	604 KB	Output is correct
6	Correct	4 ms	604 KB	Output is correct
7	Correct	4 ms	604 KB	Output is correct
8	Correct	17 ms	1336 KB	Output is correct
9	Correct	24 ms	2428 KB	Output is correct
10	Correct	26 ms	2652 KB	Output is correct
11	Correct	26 ms	2600 KB	Output is correct
12	Correct	24 ms	2640 KB	Output is correct
13	Correct	27 ms	2824 KB	Output is correct
14	Correct	28 ms	2896 KB	Output is correct
15	Correct	23 ms	3164 KB	Output is correct
16	Correct	25 ms	3104 KB	Output is correct
17	Correct	28 ms	2908 KB	Output is correct
18	Correct	28 ms	2900 KB	Output is correct
19	Correct	23 ms	3156 KB	Output is correct
20	Correct	23 ms	3156 KB	Output is correct