Submission #947379

#	Time	Username	Problem	Language	Result	Execution time	Memory
947379		hulahula3247	Mountains (IOI17_mountains)	C++17	Compilation error	0 ms	0 KiB

mountains

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define all(v) v.begin(), v.end()
const int INF = 0x3f3f3f3f;
int N;

struct Seg {

	struct Node {int s, e, l, r, v, la, lb, sa, sb;};
	vector<Node> t;
	void init(int s, int e, int v) {t.push_back({s, e, -1, -1, v, INF, 0, INF, 0});}

	void prop(int n, int s, int e) {
		if (t[n].la != INF) {
			if (t[n].la < 0) t[n].v = t[n].la*s+t[n].lb;
			else t[n].v = t[n].la*e+t[n].lb;
		}
		else t[n].v += t[n].lb;
		if (s == e) {
			t[n].la = INF;
			t[n].lb = 0;
			return;
		} 

		if (t[n].la != INF) {
			t[n].sa = t[n].la;
			t[n].sb = t[n].lb;
		}
		else t[n].sb += t[n].lb;

		if (t[n].l != -1) {
			if (t[n].la != INF) {
				t[t[n].l].la = t[n].la;
				t[t[n].l].lb = t[n].lb;
			}
			else t[t[n].l].lb += t[n].lb;
		}

		if (t[n].r != -1) {
			if (t[n].la != INF) {
				t[t[n].r].la = t[n].la;
				t[t[n].r].lb = t[n].lb;
			}
			else t[t[n].r].lb += t[n].lb;
		}

		t[n].la = INF;
		t[n].lb = 0;
	}

	void update(int n, int s, int e, int l, int r, int a, int b) {
		prop(n, s, e);
		if (l <= s && e <= r) {
			if (a == INF) t[n].lb += b;
			else {
				t[n].la = a;
				t[n].lb = b;
			}
			prop(n, s, e);
			return;
		}
		if (e < l || s > r) return;
		int m = (s+e)/2;
		if (t[n].l == -1) {
			t[n].l = t.size();
			init(s, m, 0);
			t[t[n].l].la = t[n].sa;
			t[t[n].l].lb = t[n].sb;
		}
		if (t[n].r == -1) {
			t[n].r = t.size();
			init(m+1, e, 0);
			t[t[n].r].la = t[n].sa;
			t[t[n].r].lb = t[n].sb;
		}
		update(t[n].l, s, m, l, r, a, b);
		update(t[n].r, m+1, e, l, r, a, b);
		t[n].v = max(t[t[n].l].v, t[t[n].r].v);
	}

	int get(int n, int s, int e, int idx) {
		prop(n, s, e);
		if (s == e) return t[n].v;
		int m = (s+e)/2;
		if (idx <= m) {
			if (t[n].l == -1) {
				if (e-s == 1) {
					if (t[n].sa == INF) return t[n].sb;
					else return t[n].sa*s+t[n].sb;
				}
				t[n].l = t.size();
				init(s, m, 0);
				t[t[n].l].la = t[n].sa;
				t[t[n].l].lb = t[n].sb;
			}
			return get(t[n].l, s, m, idx);
		}
		else {
			if (t[n].r == -1) {
				if (e-s == 1) {
					if (t[n].sa == INF) return t[n].sb;
					else return t[n].sa*e+t[n].sb;
				}
				t[n].r = t.size();
				init(m+1, e, 0);
				t[t[n].r].la = t[n].sa;
				t[t[n].r].lb = t[n].sb;
			}
			return get(t[n].r, m+1, e, idx);
		}
	}

	int query(int n, int s, int e, int x) {
		prop(n, s, e);
		if (s == e) {
			if (t[n].v > x) return s-1;
			else return s;
		}
		int m = (s+e)/2;

		int left;
		if (t[n].l != -1) {
			if (t[t[n].l].la == INF) left = t[t[n].l].v + t[t[n].l].lb;
			else {
				if (t[t[n].l].la < 0) left = t[t[n].l].la*s + t[t[n].l].lb;
				else left = t[t[n].l].la*m + t[t[n].l].lb;
			}
		}
		else {
			if (t[n].sa == INF) left = t[n].sb;
			else {
				if (t[n].sa < 0) left = t[n].sa*s + t[n].sb;
				else left = t[n].sa*m + t[n].sb;
			}
		}
		if (left > x) {
			if (t[n].l == -1) {
				if (e-s == 1) {
					int cur;
					if (t[n].sa == INF) cur = t[n].sb;
					else cur = t[n].sa*s+t[n].sb;
					if (cur > x) return s-1;
					else return s;
				}
				t[n].l = t.size();
				init(s, m, 0);
				t[t[n].l].la = t[n].sa;
				t[t[n].l].lb = t[n].sb;
			}
			return query(t[n].l, s, m, x);
		}
		else {
			if (t[n].r == -1) {
				if (e-s == 1) {
					int cur;
					if (t[n].sa == INF) cur = t[n].sb;
					else cur = t[n].sa*e+t[n].sb;
					if (cur > x) return e-1;
					else return e;
				}
				t[n].r = t.size();
				init(m+1, e, 0);
				t[t[n].r].la = t[n].sa;
				t[t[n].r].lb = t[n].sb;
			}
			return query(t[n].r, m+1, e, x);
		}
	}

}seg;

vector<int> arr, comp;
void solve() {

	cin >> N;
	seg.init(0, N, 0);

	while (true) {
		char op; cin >> op;
		if (op == 'I') {
			int l, r, d; cin >> l >> r >> d;
			int pv = seg.get(0, 0, N, l-1)-(l-1)*d;
			int pv2 = pv+r*d-seg.get(0, 0, N, r);
			seg.update(0, 0, N, l, r, d, pv);
			if (r != N) seg.update(0, 0, N, r+1, N, INF, pv2);
		}
		if (op == 'Q') {
			int x; cin >> x;
			cout << seg.query(0, 0, N, x) << '\n';
			//for (int i = 0; i <= N; i++) cout << seg.get(0, 0, N, i) << ' '; cout << '\n';
		}
		if (op == 'E') break;

	}

}

int main(void) {
	
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int T = 1; //cin >> T;
	while (T--) solve();
	return 0;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/cc2dn1Tc.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc4E6hmb.o:mountains.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc2dn1Tc.o: in function `main':
grader.cpp:(.text.startup+0x238): undefined reference to `maximum_deevs(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status