제출 #446357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446357		ics0503	별자리 3 (JOI20_constellation3)	C++17	100 / 100	1250 ms	439516 KiB

constellation3

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std; 
long long a[212121];
struct xy {
	long long t,x,y,c;
}all[414141]; long long an;
bool sort_y(xy a, xy b) {
	if (a.y != b.y)return a.y > b.y;
	if (a.t != b.t)return a.t < b.t;
	return a.x < b.x;
}
set<pair<pair<long long, long long>, long long>>S; long long tn;
vector<long long>edge[414141];
vector<pair<long long, long long>>qr[414141];
long long S_start[414141], S_end[414141];
vector<long long>S_ER[414141]; long long point[414141];
void insert_S(long long s, long long e,long long parent) {
	tn++;
	S.insert({ { -s,e },tn });
	S_start[tn] = s; S_end[tn] = e;
	if (parent) edge[parent].push_back(tn);
}
int pp[414141][20];
long long sparse[414141][20];;
vector<int>need_to_fill[414141][20];
void init_sparse(long long w, long long bef) {
	pp[w][0] = bef;
	for (long long i = 0; pp[w][i] != -1; i++) {
		need_to_fill[pp[w][i]][i].push_back(w);
		pp[w][i + 1] = pp[pp[w][i]][i];
	}
	for (long long nxt : edge[w]) init_sparse(nxt, w);
}
long long D[414141], depth[414141], CS[414141];
void dfs(long long w,long long bef,long long dep) {
	long long sum = 0;
	depth[w] = dep; 
	for (long long nxt : edge[w]) {
		dfs(nxt, w, dep + 1);
		sum += D[nxt];
	}
	CS[w] = sum;
	for (long long nxt : edge[w]) {
		long long v = sum - D[nxt];
		sparse[nxt][0] = v;
		for (long long i = 1; i < 20; i++) {
			for (long long who : need_to_fill[nxt][i]) {
				long long p = pp[who][i - 1];
				sparse[who][i] = sparse[p][i - 1] + sparse[who][i - 1];
			}
		}
	}
	long long qmax = 0;
	for (auto q : qr[w]) {
		long long res = q.second;
		long long now = point[q.first];
		res += CS[now];
		for (long long i = 19; i >= 0; i--) {
			long long nxt = pp[now][i];
			if (nxt == -1 || depth[nxt] <= depth[w])continue;
			res += sparse[now][i];
			now = nxt;
		}
		if(now!=w)res += sparse[now][0];
		qmax = max(qmax, res);
	}
	D[w] = max(sum, qmax);
}
int main() {
	long long n; scanf("%lld", &n);
	long long i, j;
	for (i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		all[an++] = { 1,i,a[i],0 };
	}
	long long m; scanf("%lld", &m);
	long long allS = 0;
	for (i = 1; i <= m; i++) {
		all[an].t = 2;
		scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c);
		allS += all[an].c;
		an++;
	}
	sort(all, all + an, sort_y);
	long long st, en;
	insert_S(1, n, 0);
	long long e9 = 1e9;
	for (st = 0; st < an; st = en) {
		for (en = st; all[st].y == all[en].y; en++);
		// [st, en)
		set<long long>erL;
		for (i = st; i < en; i++) {
			long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
			if (t != 1) continue;			
			auto v = S.lower_bound({ { -x,-e9 },-e9 });
			long long who = v->second;
			S_ER[who].push_back(x);
			erL.insert(who);
		}
		for (auto who : erL) {
			long long s = S_start[who], e = S_end[who];
			for (i = 0; i < S_ER[who].size(); i++) {
				long long x = S_ER[who][i];
				point[x] = who;
				long long new_st = s, new_en = x - 1;
				if (new_st <= new_en) insert_S(new_st, new_en, who);
				s = x + 1;
				if (i + 1 == S_ER[who].size()) {
					if (s <= e) insert_S(s, e, who);
				}
			}
			S.erase({ {-S_start[who],S_end[who] },who });
		}
		for (i = st; i < en; i++) {
			long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
			if (t != 2) continue;
			auto v = S.lower_bound({ { -x,-e9 },-e9 });
			if (v == S.end())continue;
			long long who = v->second;
			if(S_start[who] <= x && x <= S_end[who]) qr[who].push_back({ x, c });
		}
	}
	for (i = 1; i <= tn; i++)for (j = 0; j < 20; j++)pp[i][j] = -1;
	init_sparse(1, -1);
	dfs(1, -1, 0);
	printf("%lld\n", allS - D[1]);
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:96:42: warning: unused variable 'y' [-Wunused-variable]
   96 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                          ^
constellation3.cpp:96:56: warning: unused variable 'c' [-Wunused-variable]
   96 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                                        ^
constellation3.cpp:105:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |    for (i = 0; i < S_ER[who].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~
constellation3.cpp:111:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     if (i + 1 == S_ER[who].size()) {
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:118:42: warning: unused variable 'y' [-Wunused-variable]
  118 |    long long t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                          ^
constellation3.cpp:73:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |  long long n; scanf("%lld", &n);
      |               ~~~~~^~~~~~~~~~~~
constellation3.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   scanf("%lld", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
constellation3.cpp:79:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |  long long m; scanf("%lld", &m);
      |               ~~~~~^~~~~~~~~~~~
constellation3.cpp:83:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |   scanf("%lld%lld%lld", &all[an].x, &all[an].y, &all[an].c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65