Submission #1282512

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282512		duyanhchupapi	Team Contest (JOI22_team)	C++20	0 / 100	2 ms	3136 KiB

team

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std; 
using ll = long long; 
const int N = 150005;
int n, inf = 1e9, ans = -1;
struct kid {
	int x,y,z;
} p[N];
int comp[N], nen[N], ind, bit[N], Minz[N], seg[4*N];
////// BIT
void update(int id, int vl) {
	while(id <= ind) bit[id] = max(bit[id], vl), id += -id&id;
}
int getmax(int id) {
	int res = -1;
	while(id > 0) res = max(res, bit[id]), id -= -id&id;
	return res;
}
////////// ST
void up(int x, int l, int r, int id, int w) {
	if(l == r) {
		seg[x] = max(seg[x], w);
		return;
	}
	int m = (l+r)/2;
	if(id <= m) up(2*x,l,m,id,w);
	else up(2*x+1,m+1,r,id,w);
	seg[x] = max(seg[2*x+1], seg[2*x]);
}
int MAX(int x, int l, int r, int i, int j) {
	if(l > j || r < i) return -1;
	if(l >= i && r <= j) return seg[x];
	int m = (l+r)/2;
	return max(MAX(2*x,l,m,i,j), MAX(2*x+1,m+1,r,i,j));
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
	fill(bit, bit+N+1, -1);
	fill(seg, seg+4*N+1, -1);
	cin >> n;
	for(int i=1;i<=n;++i) cin >> p[i].x >> p[i].y >> p[i].z, comp[i] = p[i].y;
	
	sort(p+1,p+n+1, [&](const kid & p1, const kid & p2) {
		return p1.x < p2.x;
		return p1.y < p2.y;
		return p1.z < p2.z;
	});
	
	sort(comp+1,comp+n+1);
	for(int i=1;i<=n;++i) if(comp[i] != nen[ind]) nen[++ind] = comp[i];	
	for(int i=1;i<=n;++i) p[i].y = lower_bound(nen+1, nen+ind+1, p[i].y) - nen;
	
	//cout<<'\n';for(int i=1;i<=n;++i) cout<<p[i].x<<' '<<p[i].y<<' '<<p[i].z<<'\n';
	//cout<<'\n';
	int j = 1;
	for(int i=1;i<=n;i = j) {
		while(p[i].x == p[j].x) ++j;
		if(i != 1) {
			int idd = i;
			for(int id=i;id<j;id = idd) {
				while(p[id].y == p[idd].y && idd < j) ++idd;
				int Y = p[id].y, Z = p[id].z, ID = ind+1;
				int l = 1, r = ind;
				while(l <= r) {
					int mid = (l+r)/2;
					if(getmax(mid) > Z) ID = mid, r = mid - 1;
					else l = mid + 1;
				}
				
				ID = max(ID+1, Y+1);
				if(ID <= ind) ans = max(ans, p[i].x + MAX(1,1,ind,ID,ind));
			}
		}
		
		for(int id=i;id<j;++id) {
			int Y = p[id].y, Z = p[id].z;
			update(Y, Z);
			int val = getmax(Y - 1);
			if(val > Z) up(1, 1, ind, Y, val + nen[Y]);
		}
	
	}
	
	cout << ans;
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from team.cpp:1:
In function 'constexpr typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]',
    inlined from 'constexpr void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:977:21,
    inlined from 'constexpr void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
    inlined from 'int main()' at team.cpp:41:6:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 600024 bytes into a region of size 600020 overflows the destination [-Wstringop-overflow=]
  931 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~
team.cpp: In function 'int main()':
team.cpp:11:27: note: destination object 'bit' of size 600020
   11 | int comp[N], nen[N], ind, bit[N], Minz[N], seg[4*N];
      |                           ^~~
In function 'constexpr typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]',
    inlined from 'constexpr void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:977:21,
    inlined from 'constexpr void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]' at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
    inlined from 'int main()' at team.cpp:42:6:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 2400084 bytes into a region of size 2400080 overflows the destination [-Wstringop-overflow=]
  931 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~
team.cpp: In function 'int main()':
team.cpp:11:44: note: destination object 'seg' of size 2400080
   11 | int comp[N], nen[N], ind, bit[N], Minz[N], seg[4*N];
      |                                            ^~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 27