oj.uz

Submission #446361

# Submission time Handle Problem Language Result Execution time Memory
446361 2021-07-21T16:36:08 Z ics0503 Constellation 3 (JOI20_constellation3) C++17
35 / 100
 1185 ms 524288 KB 
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
using namespace std; 
int a[212121];
struct xy {
	int t,x,y,c;
}all[414141]; int 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<int, int>, int>>S; int tn;
vector<int>edge[414141];
vector<pair<int, int>>qr[414141];
int S_start[414141], S_end[414141];
vector<int>S_ER[414141]; int point[414141];
void insert_S(int s, int e,int 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(int w, int bef) {
	pp[w][0] = bef;
	for (int 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 (int nxt : edge[w]) init_sparse(nxt, w);
}
long long D[414141], depth[414141], CS[414141];
void dfs(int w,int bef,int dep) {
	long long sum = 0;
	depth[w] = dep; 
	for (int nxt : edge[w]) {
		dfs(nxt, w, dep + 1);
		sum += D[nxt];
	}
	CS[w] = sum;
	for (int nxt : edge[w]) {
		long long v = sum - D[nxt];
		sparse[nxt][0] = v;
		for (int i = 1; i < 20; i++) {
			for (int who : need_to_fill[nxt][i]) {
				int 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;
		int now = point[q.first];
		res += CS[now];
		for (int i = 19; i >= 0; i--) {
			int 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 ck[414141];
int main() {
	int n; scanf("%d", &n);
	int i, j;
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		all[an++] = { 1,i,a[i],0 };
	}
	int m; scanf("%d", &m);
	long long allS = 0;
	for (i = 1; i <= m; i++) {
		all[an].t = 2;
		scanf("%d%d%d", &all[an].x, &all[an].y, &all[an].c);
		allS += all[an].c;
		an++;
	}
	sort(all, all + an, sort_y);
	int st, en;
	insert_S(1, n, 0);
	int e9 = 1e9;
	for (st = 0; st < an; st = en) {
		for (en = st; all[st].y == all[en].y; en++);
		// [st, en)
		vector<int>erL;
		for (i = st; i < en; i++) {
			int 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 });
			int who = v->second;
			S_ER[who].push_back(x);
			ck[who] = 1;
			erL.push_back(who);
		}
		for (auto who : erL) {
			int s = S_start[who], e = S_end[who];
			for (i = 0; i < S_ER[who].size(); i++) {
				int x = S_ER[who][i];
				point[x] = who;
				int 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);
				}
			}
			ck[who] = 0;
			S.erase({ {-S_start[who],S_end[who] },who });
		}
		for (i = st; i < en; i++) {
			int 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;
			int 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;
}

Compilation message

constellation3.cpp: In function 'int main()':
constellation3.cpp:97:36: warning: unused variable 'y' [-Wunused-variable]
   97 |    int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                    ^
constellation3.cpp:97:50: warning: unused variable 'c' [-Wunused-variable]
   97 |    int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                                  ^
constellation3.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |    for (i = 0; i < S_ER[who].size(); i++) {
      |                ~~^~~~~~~~~~~~~~~~~~
constellation3.cpp:113:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     if (i + 1 == S_ER[who].size()) {
      |         ~~~~~~^~~~~~~~~~~~~~~~~~~
constellation3.cpp:121:36: warning: unused variable 'y' [-Wunused-variable]
  121 |    int t = all[i].t, x = all[i].x, y = all[i].y, c = all[i].c;
      |                                    ^
constellation3.cpp:74:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |  int n; scanf("%d", &n);
      |         ~~~~~^~~~~~~~~~
constellation3.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
constellation3.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |  int m; scanf("%d", &m);
      |         ~~~~~^~~~~~~~~~
constellation3.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |   scanf("%d%d%d", &all[an].x, &all[an].y, &all[an].c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 224068 KB Output is correct
2 Correct 144 ms 224172 KB Output is correct
3 Correct 147 ms 224048 KB Output is correct
4 Correct 143 ms 224160 KB Output is correct
5 Correct 149 ms 224068 KB Output is correct
6 Correct 146 ms 224248 KB Output is correct
7 Correct 141 ms 224116 KB Output is correct
8 Correct 142 ms 224128 KB Output is correct
9 Correct 141 ms 224040 KB Output is correct
10 Correct 141 ms 224104 KB Output is correct
11 Correct 148 ms 224116 KB Output is correct
12 Correct 144 ms 224056 KB Output is correct
13 Correct 142 ms 224068 KB Output is correct
14 Correct 144 ms 224316 KB Output is correct
15 Correct 145 ms 224188 KB Output is correct
16 Correct 144 ms 224196 KB Output is correct
17 Correct 141 ms 224152 KB Output is correct
18 Correct 143 ms 224140 KB Output is correct
19 Correct 146 ms 224196 KB Output is correct
20 Correct 144 ms 224124 KB Output is correct
21 Correct 140 ms 224132 KB Output is correct
22 Correct 147 ms 224136 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 224068 KB Output is correct
2 Correct 144 ms 224172 KB Output is correct
3 Correct 147 ms 224048 KB Output is correct
4 Correct 143 ms 224160 KB Output is correct
5 Correct 149 ms 224068 KB Output is correct
6 Correct 146 ms 224248 KB Output is correct
7 Correct 141 ms 224116 KB Output is correct
8 Correct 142 ms 224128 KB Output is correct
9 Correct 141 ms 224040 KB Output is correct
10 Correct 141 ms 224104 KB Output is correct
11 Correct 148 ms 224116 KB Output is correct
12 Correct 144 ms 224056 KB Output is correct
13 Correct 142 ms 224068 KB Output is correct
14 Correct 144 ms 224316 KB Output is correct
15 Correct 145 ms 224188 KB Output is correct
16 Correct 144 ms 224196 KB Output is correct
17 Correct 141 ms 224152 KB Output is correct
18 Correct 143 ms 224140 KB Output is correct
19 Correct 146 ms 224196 KB Output is correct
20 Correct 144 ms 224124 KB Output is correct
21 Correct 140 ms 224132 KB Output is correct
22 Correct 147 ms 224136 KB Output is correct
23 Correct 144 ms 224836 KB Output is correct
24 Correct 146 ms 224864 KB Output is correct
25 Correct 147 ms 224864 KB Output is correct
26 Correct 148 ms 224892 KB Output is correct
27 Correct 151 ms 224820 KB Output is correct
28 Correct 144 ms 224836 KB Output is correct
29 Correct 145 ms 224872 KB Output is correct
30 Correct 146 ms 224872 KB Output is correct
31 Correct 145 ms 224744 KB Output is correct
32 Correct 147 ms 225244 KB Output is correct
33 Correct 147 ms 225132 KB Output is correct
34 Correct 145 ms 224956 KB Output is correct
35 Correct 144 ms 224952 KB Output is correct
36 Correct 147 ms 226016 KB Output is correct
37 Correct 145 ms 226884 KB Output is correct
38 Correct 150 ms 225524 KB Output is correct
39 Correct 145 ms 224972 KB Output is correct
40 Correct 145 ms 225184 KB Output is correct
41 Correct 144 ms 225328 KB Output is correct
42 Correct 146 ms 225072 KB Output is correct
43 Correct 144 ms 225264 KB Output is correct
44 Correct 144 ms 225348 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 224068 KB Output is correct
2 Correct 144 ms 224172 KB Output is correct
3 Correct 147 ms 224048 KB Output is correct
4 Correct 143 ms 224160 KB Output is correct
5 Correct 149 ms 224068 KB Output is correct
6 Correct 146 ms 224248 KB Output is correct
7 Correct 141 ms 224116 KB Output is correct
8 Correct 142 ms 224128 KB Output is correct
9 Correct 141 ms 224040 KB Output is correct
10 Correct 141 ms 224104 KB Output is correct
11 Correct 148 ms 224116 KB Output is correct
12 Correct 144 ms 224056 KB Output is correct
13 Correct 142 ms 224068 KB Output is correct
14 Correct 144 ms 224316 KB Output is correct
15 Correct 145 ms 224188 KB Output is correct
16 Correct 144 ms 224196 KB Output is correct
17 Correct 141 ms 224152 KB Output is correct
18 Correct 143 ms 224140 KB Output is correct
19 Correct 146 ms 224196 KB Output is correct
20 Correct 144 ms 224124 KB Output is correct
21 Correct 140 ms 224132 KB Output is correct
22 Correct 147 ms 224136 KB Output is correct
23 Correct 144 ms 224836 KB Output is correct
24 Correct 146 ms 224864 KB Output is correct
25 Correct 147 ms 224864 KB Output is correct
26 Correct 148 ms 224892 KB Output is correct
27 Correct 151 ms 224820 KB Output is correct
28 Correct 144 ms 224836 KB Output is correct
29 Correct 145 ms 224872 KB Output is correct
30 Correct 146 ms 224872 KB Output is correct
31 Correct 145 ms 224744 KB Output is correct
32 Correct 147 ms 225244 KB Output is correct
33 Correct 147 ms 225132 KB Output is correct
34 Correct 145 ms 224956 KB Output is correct
35 Correct 144 ms 224952 KB Output is correct
36 Correct 147 ms 226016 KB Output is correct
37 Correct 145 ms 226884 KB Output is correct
38 Correct 150 ms 225524 KB Output is correct
39 Correct 145 ms 224972 KB Output is correct
40 Correct 145 ms 225184 KB Output is correct
41 Correct 144 ms 225328 KB Output is correct
42 Correct 146 ms 225072 KB Output is correct
43 Correct 144 ms 225264 KB Output is correct
44 Correct 144 ms 225348 KB Output is correct
45 Correct 1044 ms 310652 KB Output is correct
46 Correct 1020 ms 309588 KB Output is correct
47 Correct 1000 ms 308656 KB Output is correct
48 Correct 1107 ms 310980 KB Output is correct
49 Correct 1044 ms 308096 KB Output is correct
50 Correct 975 ms 308036 KB Output is correct
51 Correct 988 ms 308104 KB Output is correct
52 Correct 1037 ms 310084 KB Output is correct
53 Correct 1125 ms 309908 KB Output is correct
54 Correct 1185 ms 380484 KB Output is correct
55 Correct 1060 ms 356132 KB Output is correct
56 Correct 1002 ms 343960 KB Output is correct
57 Correct 921 ms 335996 KB Output is correct
58 Runtime error 758 ms 524288 KB Execution killed with signal 11
59 Halted 0 ms 0 KB -