Submission #47705

#	Time	Username	Problem	Language	Result	Execution time	Memory
47705		E869120	Fireworks (APIO16_fireworks)	C++14	100 / 100	1854 ms	467352 KiB

fireworks

#include <iostream>
#include <vector>
#include <map>
#include <functional>
#include <algorithm>
using namespace std;
#pragma warning (disable: 4996)

struct Node {
	int num, l, r;
};

class SugoyDataStructure {
public:
	vector<Node>vec; int size_ = 0; long long sum = 0;

	void init() {
		vec.push_back(Node{ 0,-1,-1 });
		size_ = 1;
	}
	void add(long long pos, long long x) {
		long long cx = 0; pos -= sum;
		for (int i = 49; i >= 0; i--) {
			vec[cx].num += x;
			if (pos >= (1LL << i)) {
				if (vec[cx].r >= 0) cx = vec[cx].r;
				else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].r = size_; cx = size_; size_++; }
				pos -= (1LL << i);
			}
			else {
				if (vec[cx].l >= 0) cx = vec[cx].l;
				else { vec.push_back(Node{ 0,-1,-1 }); vec[cx].l = size_; cx = size_; size_++; }
			}
		}
		vec[cx].num += x;
	}
	int getsize() {
		return vec[0].num;
	}
	long long getvalue(int p) {
		long long cx = 0, D = 0;
		for (int i = 49; i >= 0; i--) {
			if (vec[cx].l >= 0 && p < vec[vec[cx].l].num) cx = vec[cx].l;
			else { if (vec[cx].l >= 0) { p -= vec[vec[cx].l].num; } cx = vec[cx].r; D += (1LL << i); }
		}
		return D + sum;
	}
	void AddToSum(long long x) {
		sum += x;
	}
};

long long N, M, A[300009], B[300009], dist[300009], rem; vector<pair<long long, long long>>G[300009];
long long P[300009]; SugoyDataStructure F[300009];

int main() {
	cin >> N >> M;
	for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
	for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }

	for (int i = N + M; i >= 1; i--) {
		if (G[i].size() == 0) {
			F[i].init(); P[i] = i;
			F[i].add(dist[i], 2);
		}
		else {
			vector<pair<long long, long long>>A; long long res = 0;
			for (int j = 0; j < G[i].size(); j++) {
				int to = G[i][j].first, L = F[P[to]].getsize();
				A.push_back(make_pair(L, P[to])); res += L;
			}
			sort(A.begin(), A.end(), greater<pair<long long, long long>>());

			int S = A[0].second;
			if (i == 1) { S = 1; F[S].init(); }
			P[i] = S;
			for (int j = 0; j < G[i].size(); j++) {
				int to = G[i][j].first, v = P[to];
				if (v == S) continue;

				for (int k = 0; k < F[v].getsize(); k++) F[S].add(F[v].getvalue(k), 1);
			}
			for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
			long long D = F[S].getsize();
			long long v1 = F[S].getvalue(D - 2), v2 = F[S].getvalue(D - 1);

			F[S].AddToSum(-B[i]);
			F[S].add(v1 - B[i], -1); F[S].add(v1, 1);
			F[S].add(v2 - B[i], -1); F[S].add(v2, 1);
		}
		//cout << i << ": "; for (int j = 0; j < F[P[i]].getsize(); j++) cout << F[P[i]].getvalue(j) << " "; cout << endl;
	}
	long long LastAnswer = rem, cx = 0;
	for (int i = 0; i < F[1].getsize() - 1; i++) {
		long long val = F[1].getvalue(i); //cout << val << endl;
		LastAnswer -= (F[1].getsize() - i - 1)*(val - cx); cx = val;
	}
	cout << LastAnswer << endl;
	return 0;
}

Compilation message (stderr)

fireworks.cpp:7:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning (disable: 4996)
 
fireworks.cpp: In function 'int main()':
fireworks.cpp:59:55: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i <= N + M; i++) { for (int j = 0; j < G[i].size(); j++) dist[G[i][j].first] += dist[i] + G[i][j].second; }
                                                     ~~^~~~~~~~~~~~~
fireworks.cpp:68:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
fireworks.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size(); j++) {
                    ~~^~~~~~~~~~~~~
fireworks.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 0; j < G[i].size() - 1; j++) { long long v1 = F[S].getvalue(F[S].getsize() - 1); F[S].add(v1, -1); }
                    ~~^~~~~~~~~~~~~~~~~
fireworks.cpp:58:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 2; i <= N + M; i++) { scanf("%lld%lld", &A[i], &B[i]); rem += B[i]; G[A[i]].push_back(make_pair(i, B[i])); }
                                     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 19 / 19
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45