Submission #1283352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283352		polarity	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	1 ms	332 KiB

apple

/**
 * Solution by Charles Ran (polarity.sh)
 * Date: 2025-10-25
 * Contest: IZhO 2012
 * Problem: apple
**/

#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using pii = pair<int, int>;
#define pb push_back
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const int MAX_N = 1e5 + 1;
const ll MOD = 1e9 + 7;

/**
 * DATASTRUCTURE: Sparse Segment Tree
 * PURPOSE: Lazy Segment Tree on large intervals
 * TIME: O(log n)
 * MEMORY: O(q log n)
 * SOURCE: KACTL
 */
// static char buf[450 << 20];
// void* operator new(size_t s) {
// 	static size_t i = sizeof buf;
// 	assert(s < i);
// 	return (void*)&buf[i -= s];
// }
// void operator delete(void*) {}
// template<class T> struct ptr {
// 	unsigned ind;
// 	ptr(T* p = 0) : ind(p ? unsigned((char*)p - buf) : 0) {
// 		assert(ind < sizeof buf);
// 	}
// 	T& operator*() const { return *(T*)(buf + ind); }
// 	T* operator->() const { return &**this; }
// 	T& operator[](int a) const { return (&**this)[a]; }
// 	explicit operator bool() const { return ind; }
// };
ll combine(ll x, ll y){
    return x + y;
}
struct Node {
	Node *l = 0, *r = 0;
    ll unit = 0;
	ll lo, hi, mset = unit, madd = 0, val = unit;
	Node(ll lo,ll hi):lo(lo),hi(hi){} // Large interval of -unit
	Node(vi& v, ll lo, ll hi) : lo(lo), hi(hi) {
		if (lo + 1 < hi) {
			ll mid = lo + (hi - lo)/2;
			l = new Node(v, lo, mid); r = new Node(v, mid, hi);
			val = combine(l->val, r->val);
		}
		else val = v[lo];
	}
    // NOTE: [L, R)
	ll query(ll L, ll R) {
		if (R <= lo || hi <= L) return unit;
		if (L <= lo && hi <= R) return val;
		push();
		return combine(l->query(L, R), r->query(L, R));
	}
	void set(ll L, ll R, ll x) {
		if (R <= lo || hi <= L) return;
        ll range = hi - lo;
		if (L <= lo && hi <= R) mset = x, val = x * range, madd = 0;
		else {
			push(), l->set(L, R, x), r->set(L, R, x);
			val = combine(l->val, r->val);
		}
	}
	void add(ll L, ll R, ll x) {
		if (R <= lo || hi <= L) return;
        ll range = hi - lo + 1;
		if (L <= lo && hi <= R) {
			if (mset != unit) mset += x;
			else madd += x;
			val += x * range;
		}
		else {
			push(), l->add(L, R, x), r->add(L, R, x);
			val = combine(l->val, r->val);
		}
	}
	void push() {
		if (!l) {
			ll mid = lo + (hi - lo)/2;
			l = new Node(lo, mid); r = new Node(mid, hi);
		}
		if (mset != unit)
			l->set(lo,hi,mset), r->set(lo,hi,mset), mset = unit;
		else if (madd)
			l->add(lo,hi,madd), r->add(lo,hi,madd), madd = 0;
	}
};

void releaseNode(Node* n)
{
    if (!n) return;
    releaseNode(n->l);
    releaseNode(n->r);
    delete n;
}

const string iofilename = "f";
ifstream fin(iofilename + ".in");
ofstream fout(iofilename + ".out");

// Use fstream (fin, fout) instead of iostream!
void solve(){
    int m; cin >> m;

    Node segtree(0, 1e9 + 1);

    int add = 0;
    rep(i, 0, m){
        int c; cin >> c;
        int x, y;  cin >> x >> y;
        x += add;
        y += add + 1;

        if (c == 1){
            add = segtree.query(x, y);
            cout << add << endl;    
        } else {
            segtree.set(x, y, 1);
        }
    }

    releaseNode(&segtree);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    solve();
    return 0;
}

Compilation message (stderr)

In function 'void releaseNode(Node*)',
    inlined from 'void releaseNode(Node*)' at apple.cpp:105:6,
    inlined from 'void solve()' at apple.cpp:138:16:
apple.cpp:110:12: warning: 'void operator delete(void*, std::size_t)' called on unallocated object 'segtree' [-Wfree-nonheap-object]
  110 |     delete n;
      |            ^
apple.cpp: In function 'void solve()':
apple.cpp:121:10: note: declared here
  121 |     Node segtree(0, 1e9 + 1);
      |          ^~~~~~~

• Subtask 1: 0 / 100