oj.uz

Submission #774004

# Submission time Handle Problem Language Result Execution time Memory
774004 2023-07-05T10:44:08 Z SanguineChameleon Distributing Candies (IOI21_candies) C++17
32 / 100
 575 ms 42648 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

const int inf = 1e9 + 20;
const int maxN = 2e5 + 20;
vector<pair<int, int>> events[maxN];

struct node {
	long long mx, mi, lazy;

	node(): mx(0), mi(0), lazy(0) {};

	node(long long _mx, long long _mi): mx(_mx), mi(_mi), lazy(0) {};
};

node tree[maxN * 4];

node merge(node left, node right) {
	return node(max(left.mx, right.mx), min(left.mi, right.mi));
}

void add(int id, int val) {
	tree[id].mx += val;
	tree[id].mi += val;
	tree[id].lazy += val;
}

void push(int id) {
	add(id * 2, tree[id].lazy);
	add(id * 2 + 1, tree[id].lazy);
	tree[id].lazy = 0;
}

void update(int id, int lt, int rt, int pos, int val) {
	if (lt == rt) {
		add(id, val);
		return;
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (pos >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, pos, val);
	}
	else {
		add(id * 2 + 1, val);
		update(id * 2, lt, mt, pos, val);
	}
	tree[id] = merge(tree[id * 2], tree[id * 2 + 1]);
}

node get(int id, int lt, int rt, int pos) {
	if (lt == rt) {
		return tree[id];
	}
	push(id);
	int mt = (lt + rt) / 2;
	if (pos >= mt + 1) {
		return get(id * 2 + 1, mt + 1, rt, pos);
	}
	else {
		return merge(get(id * 2, lt, mt, pos), tree[id * 2 + 1]);
	}
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	int N = C.size();
	int Q = L.size() + 2;
	for (int i = 0; i < Q - 2; i++) {
		events[L[i]].emplace_back(i + 3, V[i]);
		events[R[i] + 1].emplace_back(i + 3, -V[i]);
	}
	update(1, 1, Q, 1, inf);
	update(1, 1, Q, 2, -inf);
	vector<int> res(N);
	long long sum = 0;
	for (int i = 0; i < N; i++) {
		for (auto e: events[i]) {
			update(1, 1, Q, e.first, e.second);
			sum += e.second;
		}
		int lt = 1;
		int rt = Q;
		int last = -1;
		while (lt <= rt) {
			int mt = (lt + rt) / 2;
			node M = get(1, 1, Q, mt);
			if (M.mx - M.mi <= C[i]) {
				last = mt;
				rt = mt - 1;
			}
			else {
				lt = mt + 1;
			}
		}
		node M1 = get(1, 1, Q, last);
		node M2 = get(1, 1, Q, last - 1);
		res[i] = sum - (M1.mi == M2.mi ? M1.mi : (M1.mx - C[i]));
	}
	return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23784 KB Output is correct
2 Correct 10 ms 23676 KB Output is correct
3 Correct 11 ms 23800 KB Output is correct
4 Correct 11 ms 23872 KB Output is correct
5 Correct 13 ms 23928 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 575 ms 42648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23764 KB Output is correct
2 Incorrect 161 ms 35976 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23788 KB Output is correct
2 Correct 11 ms 23784 KB Output is correct
3 Correct 96 ms 34408 KB Output is correct
4 Correct 174 ms 27556 KB Output is correct
5 Correct 492 ms 37504 KB Output is correct
6 Correct 532 ms 38172 KB Output is correct
7 Correct 432 ms 38888 KB Output is correct
8 Correct 494 ms 37424 KB Output is correct
9 Correct 541 ms 38880 KB Output is correct

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23784 KB Output is correct
2 Correct 10 ms 23676 KB Output is correct
3 Correct 11 ms 23800 KB Output is correct
4 Correct 11 ms 23872 KB Output is correct
5 Correct 13 ms 23928 KB Output is correct
6 Incorrect 575 ms 42648 KB Output isn't correct
7 Halted 0 ms 0 KB -