Submission #552662

#	Time	Username	Problem	Language	Result	Execution time	Memory
552662		GioChkhaidze	Team Contest (JOI22_team)	C++14	100 / 100	939 ms	72716 KiB

team

#include <bits/stdc++.h>
 
#define lf (h << 1)
#define mf ((l + r) >> 1)
#define rf ((h << 1) | 1)
#define tree int h, int l, int r
#define left lf, l, mf
#define right rf, mf + 1, r
#define ll long long
#define pb push_back
#define f first
#define s second
 
using namespace std;
 
const int N = 150005;
 
int n, x[N], y[N], z[N], Ox[N], Oy[N], Oz[N];
vector < int > vx[N], vy[N], vz[N];
vector < pair < int , int > > G[N];
int v[5 * N][3];
 
inline void upd(tree, int id, int vl, bool tp) {
	if (r < id || id < l) return ;
	if (l == id && id == r) {
		v[h][tp] = max(v[h][tp], vl);
		return ;
	}
	upd(left, id, vl, tp);
	upd(right, id, vl, tp);
	v[h][tp] = max(v[lf][tp], v[rf][tp]);
}

inline int get(tree, int L, int R, bool tp) {
	if (r < L || R < l) return 0;
	if (L <= l && r <= R) return v[h][tp];
	return max(get(left, L, R, tp), get(right, L, R, tp));
}

main () {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	
	cin >> n;
	vector < int > sx, sy, sz, s;
	map < int , int > fx, fy, fz;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i] >> z[i];
		sx.pb(x[i]);
		sy.pb(y[i]);
		sz.pb(z[i]);
		s.pb(i);
	}
	sort(sx.begin(), sx.end());
	sort(sy.begin(), sy.end());
	sort(sz.begin(), sz.end());
	sx.erase(unique(sx.begin(), sx.end()), sx.end());
	sy.erase(unique(sy.begin(), sy.end()), sy.end());
	sz.erase(unique(sz.begin(), sz.end()), sz.end());
	for (int i = 0; i < sx.size(); ++i) fx[sx[i]] = i + 1, Ox[i + 1] = sx[i];
	for (int i = 0; i < sy.size(); ++i) fy[sy[i]] = i + 1, Oy[i + 1] = sy[i];
	for (int i = 0; i < sz.size(); ++i) fz[sz[i]] = i + 1, Oz[i + 1] = sz[i];
	
	for (int i = 1; i <= n; ++i) {
		x[i] = fx[x[i]];
		y[i] = fy[y[i]];
		z[i] = fz[z[i]];
	}

	for (int i = 1; i <= n; ++i) {
		vx[x[i]].pb(i);
		vy[y[i]].pb(i);
		vz[z[i]].pb(i);
	}
	
	for (int i = 1; i <= sx.size(); ++i) {
		for (int j = 0; j < vx[i].size(); ++j) {
			int id = vx[i][j];	
			upd(1, 1, sy.size(), y[id], z[id], 0);
			upd(1, 1, sz.size(), z[id], y[id], 1);
		}
		
		for (int j = 0; j < vx[i].size(); ++j) {
			int id = vx[i][j];
			int Z = get(1, 1, sy.size(), 1, y[id] - 1, 0); 
			int Y = get(1, 1, sz.size(), 1, z[id] - 1, 1);

			if (z[id] < Z) {
				G[y[id]].pb({x[id], Z});
 			}
			
			if (y[id] < Y) {
				G[Y].pb({x[id], z[id]});
			}
		}
	}
	
	for (int i = 1; i <= 5 * n; ++i) {
		v[i][0] = v[i][1] = 0;
	}
	
	int ans = -1;
	for (int i = 1; i <= sy.size(); ++i) {
		for (int j = 0; j < G[i].size(); ++j) {
			int xid = G[i][j].f, zid = G[i][j].s;
			int X = get(1, 1, sz.size(), 1, zid - 1, 1);
			if (xid < X) {
				ans = max(ans, Ox[X] + Oy[i] + Oz[zid]);
			}
		}
		for (int j = 0; j < vy[i].size(); ++j) {
			int id = vy[i][j];
			upd(1, 1, sz.size(), z[id], x[id], 1);
		}
	}
	
	cout << ans << "\n";
}

Compilation message (stderr)

team.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main () {
      | ^~~~
team.cpp: In function 'int main()':
team.cpp:60:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for (int i = 0; i < sx.size(); ++i) fx[sx[i]] = i + 1, Ox[i + 1] = sx[i];
      |                  ~~^~~~~~~~~~~
team.cpp:61:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for (int i = 0; i < sy.size(); ++i) fy[sy[i]] = i + 1, Oy[i + 1] = sy[i];
      |                  ~~^~~~~~~~~~~
team.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for (int i = 0; i < sz.size(); ++i) fz[sz[i]] = i + 1, Oz[i + 1] = sz[i];
      |                  ~~^~~~~~~~~~~
team.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for (int i = 1; i <= sx.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
team.cpp:77:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |   for (int j = 0; j < vx[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~~
team.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int j = 0; j < vx[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~~
team.cpp:103:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for (int i = 1; i <= sy.size(); ++i) {
      |                  ~~^~~~~~~~~~~~
team.cpp:104:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |   for (int j = 0; j < G[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~
team.cpp:111:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |   for (int j = 0; j < vy[i].size(); ++j) {
      |                   ~~^~~~~~~~~~~~~~

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