oj.uz

답안 #817142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
817142 2023-08-09T09:49:02 Z GEN 이지후(#10378) Ants and Sugar (JOI22_sugar) C++17
0 / 100
 826 ms 127356 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()
const int MAXT = 1050000;

struct bit {
	lint tree[MAXT];
	void add(int x, lint v) {
		for (int i = x + 2; i < MAXT; i += i & -i)
			tree[i] += v;
	}
	lint query(int x) {
		lint ret = 0;
		for (int i = x + 2; i; i -= i & -i)
			ret += tree[i];
		return ret;
	}
} bit;

lint l;

vector<lint> vect;
struct node {
	lint adj[3][3], lazy;
	node() {
		lazy = 0;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				adj[i][j] = -1e18;
			}
		}
	}
	void addLazy(lint x, int pos) {
		lazy += x;
		adj[0][1] -= x;
		adj[0][2] -= x;
		adj[2][1] -= x;
	}
	node operator+(const node &nd) const {
		node ret;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					ret.adj[j][k] = max(ret.adj[j][k], adj[j][i] + nd.adj[i][k]);
				}
			}
		}
		return ret;
	}
} tree[MAXT];

void init(int s, int e, int p, vector<node> &v) {
	if (s == e) {
		tree[p] = v[s];
		return;
	}
	int m = (s + e) / 2;
	init(s, m, 2 * p, v);
	init(m + 1, e, 2 * p + 1, v);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

void lazydown(int p, int ps, int pm) {
	if (tree[p].lazy) {
		for (int i = 2 * p; i < 2 * p + 2; i++) {
			tree[i].addLazy(tree[p].lazy, (i % 2 ? (pm + 1) : ps));
		}
		tree[p].lazy = 0;
	}
}
void upd(int pos, int s, int e, int p, node v) {
	if (s == e) {
		tree[p] = v;
		return;
	}
	int m = (s + e) / 2;
	lazydown(p, s, m);

	if (pos <= m)
		upd(pos, s, m, 2 * p, v);
	else
		upd(pos, m + 1, e, 2 * p + 1, v);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

void lazy(int s, int e, int ps, int pe, int p, lint v) {
	if (e < ps || pe < s)
		return;
	if (s <= ps && pe <= e) {
		tree[p].addLazy(v, ps);
		return;
	}
	int pm = (ps + pe) / 2;
	lazydown(p, ps, pm);
	lazy(s, e, ps, pm, 2 * p, v);
	lazy(s, e, pm + 1, pe, 2 * p + 1, v);
	tree[p] = tree[2 * p] + tree[2 * p + 1];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	lint q;
	cin >> q >> l;
	vector<array<lint, 3>> qry(q);
	for (int i = 0; i < q; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> qry[i][j];
		}
		if (qry[i][0] == 1) {
			qry[i][1] -= l;
		}
		if (qry[i][0] == 2)
			vect.push_back(qry[i][1]);
	}
	if (sz(vect) == 0) {
		while (q--)
			cout << "0\n";
		return 0;
	}
	sort(all(vect));
	vect.resize(unique(all(vect)) - vect.begin());
	// (my weight, R mode, T mode)
	vector<array<lint, 2>> values(sz(vect));
	auto genNode = [&](int pos) {
		node ret;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j < 3; j++) {
				if (j == 0)
					ret.adj[i][j] = 0;
				if (j == 1)
					if (i == 0)
						ret.adj[i][j] = values[pos][0] - bit.query(pos);
				if (j == 2) {
					if (i > 0 && (pos > 0 && vect[pos] - vect[pos - 1] <= 2 * l)) {
						ret.adj[i][j] = values[pos][0] - values[pos][1];
					} else
						ret.adj[i][j] = -1e18;
				}
			}
		}
		return ret;
	};
	vector<node> nodes;
	for (int i = 0; i < sz(vect); i++) {
		nodes.push_back(genNode(i));
	}
	init(0, sz(vect) - 1, 1, nodes);
	lint sugsum = 0;
	for (int i = 0; i < q; i++) {
		if (qry[i][0] == 1) {
			int st = lower_bound(all(vect), qry[i][1]) - vect.begin();
			int ed = lower_bound(all(vect), qry[i][1] + 2 * l + 1) - vect.begin();
			if (st < sz(vect)) {
				values[st][1] += qry[i][2];
				upd(st, 0, sz(vect) - 1, 1, genNode(st));
			}
			if (st < ed) {
				bit.add(st, qry[i][2]);
				bit.add(ed, -qry[i][2]);
				lazy(st + 1, ed - 1, 0, sz(vect) - 1, 1, qry[i][2]);
				upd(st, 0, sz(vect) - 1, 1, genNode(st));
			}
		} else {
			auto it = lower_bound(all(vect), qry[i][1]) - vect.begin();
			values[it][0] += qry[i][2];
			sugsum += qry[i][2];
			upd(it, 0, sz(vect) - 1, 1, genNode(it));
		}
		cout << sugsum - *max_element(tree[1].adj[0], tree[1].adj[0] + 3) << "\n";
	}
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 82504 KB Output is correct
2 Incorrect 33 ms 82516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 82560 KB Output is correct
2 Incorrect 32 ms 82452 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 82452 KB Output is correct
2 Correct 374 ms 102588 KB Output is correct
3 Correct 501 ms 115128 KB Output is correct
4 Correct 826 ms 127320 KB Output is correct
5 Correct 781 ms 127356 KB Output is correct
6 Incorrect 780 ms 117920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 82504 KB Output is correct
2 Incorrect 33 ms 82516 KB Output isn't correct
3 Halted 0 ms 0 KB -