Submission #561168

---

Source Code Expand

#include <iostream>
#include <cmath>
#include <cassert>

using namespace std;
typedef long long ll;
typedef pair<int, ll> P;

struct AA {
	using NP = AA*;
	ll sm;
	bool lz;
	NP l, r;
	ll sz; int lv;
	bool isL; // is last
	AA(ll sz, bool lz) : l(nullptr), r(nullptr), sz(sz), lv(0), isL(true) {
		if (lz) {
			sm = 0;
		} else {
			sm = sz;
		}
		this->lz = lz;
	}
	AA(NP l, NP r, int lv) : l(l), r(r), lv(lv), isL(false) {
		lz = false;
		update();
	}
	void update() {
		assert(!lz);
		sz = l->sz + r->sz;
		sm = l->sm + r->sm;
	}
	void push() {
		if (lz) {
			if (l->sz) {
				l->lzdata();
			}
			if (r->sz) {
				r->lzdata();
			}
			lz = false;
		}
	}
	void lzdata() {
		sm = 0;
		lz = true;
	}
	static NP skew(NP n) {
		if (n->l == nullptr || n->lv != n->l->lv) return n;
		NP L = n->l;
		n->l = L->r;
		n->update();
		L->r = n;
		L->update();
		return L;
	}
	static NP pull(NP n) {
		if (n->r == nullptr || n->lv != n->r->lv) return n;
		if (n->r->r == nullptr || n->lv != n->r->r->lv) return n;
		NP R = n->r;
		n->r = R->l;
		n->update();
		R->l = n;
		R->lv++;
		R->update();
		return R;
	}
	static NP inscut(NP n, ll k) {
		if (k == 0 || k == n->sz) return n;
		if (n->isL) {
			return new AA(new AA(k, n->lz), new AA(n->sz - k, n->lz), 1);
		}
		n->push();
		if (k <= n->l->sz) {
			n->l = inscut(n->l, k);
			n->update();
			return pull(skew(n));
		} else {
			n->r = inscut(n->r, k - n->l->sz);
			n->update();
			return pull(skew(n));
		}
	}
	static ll get(NP n, ll a, ll b) {
		if (b <= 0 || n->sz <= a) return 0;
		if (a <= 0 && n->sz <= b) return n->sm;
		n->push();
		return get(n->l, a, b) + get(n->r, a - n->l->sz, b - n->l->sz);
	}
	static void set(NP n, ll a, ll b) {
		if (b <= 0 || n->sz <= a) return;
		if (a <= 0 && n->sz <= b) {
			n->lzdata();
			return;
		}
		assert(n->isL == false);
		set(n->l, a, b);
		set(n->r, a - n->l->sz, b - n->l->sz);
		n->update();
	}

    static ll sea(NP n, ll x) {
    	assert(x < n->sm);
    	if (n->isL) {
    		assert(!n->lz);
    		return x;
    	}
    	n->push();
    	if (x < n->l->sm) {
    		return sea(n->l, x);
    	} else {
    		return n->l->sz + sea(n->r, x - n->l->sm);
    	}
    }
};

 
int main() {
	int n;
	scanf("%d", &n);
	AA* t2 = new AA(1e18 + 1e17, false);
	for (int i = 0; i < n; i++) {
		ll s, c;
		scanf("%lld %lld", &s, &c);
		t2 = AA::inscut(t2, 0);
		t2 = AA::inscut(t2, s);
		ll fi = AA::get(t2, 0, s);
		ll l = AA::sea(t2, c+fi-1);
		t2 = AA::inscut(t2, s);
		t2 = AA::inscut(t2, l+1);
		AA::set(t2, s, l+1);
		printf("%lld\n", l);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:120:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
./Main.cpp:124:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld", &s, &c);
                             ^

Judge Result