Submission #1282381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282381		c4l	Team Contest (JOI22_team)	C++20	55 / 100	2049 ms	653836 KiB

team

#include <bits/stdc++.h>
// #define int long long
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL;
const int BUF_SZ = 1 << 15;

inline namespace Input {
char buf[BUF_SZ];
int pos = 0;
int len = 0;
char next_char() {
	if (pos == len) {
		pos = 0;
		len = (int)fread(buf, 1, BUF_SZ, stdin);
		if (!len) { return EOF; }
	}
	return buf[pos++];
}

// đọc 64-bit signed
ll read_ll() {
	ll x = 0;
	char ch;
	int sgn = 1;
	// skip đến digit hoặc dấu '-'
	while (!isdigit(ch = next_char())) {
		if (ch == '-') { sgn = -1; break; }
	}
	// nếu vừa gặp '-', lấy char tiếp theo (nếu là EOF thì behavior như cũ của bạn)
	if (ch == '-') ch = next_char();
	x = ch - '0';
	while (isdigit(ch = next_char())) {
		x = x * 10 + (ch - '0');
	}
	return x * sgn;
}
} // namespace Input

inline namespace Output {
char buf[BUF_SZ];
int pos = 0;

void flush_out() {
	fwrite(buf, 1, pos, stdout);
	pos = 0;
}

void write_char(char c) {
	if (pos == BUF_SZ) flush_out();
	buf[pos++] = c;
}

void write_ll(ll x) {
	static char num_buf[100];
	if (x < 0) write_char('-');
	// chuyển sang unsigned để xử lý LLONG_MIN đúng
	unsigned long long ux = x < 0 ? (unsigned long long)(-(x + 1)) + 1ULL : (unsigned long long)x;
	int len = 0;
	while (ux >= 10ULL) {
		num_buf[len++] = char('0' + (ux % 10ULL));
		ux /= 10ULL;
	}
	write_char(char('0' + ux));
	while (len) write_char(num_buf[--len]);
	write_char('\n');
}

void init_output() { assert(atexit(flush_out) == 0); }
} // namespace Output

struct mem{
	int x, y, z;
};
mem a[150001];
vector<int> luu[300005];
vector<int> tr[300005];
vector<int> trz[300005];
int inf = -1e9;
int n;
struct pst{
	struct Node{
		int val;
		int l, r;
		Node(int v){
			val = v;
			l = -1, r= -1;
		}
	};
	vector<Node> luu;
	void clear(){
		luu.clear();
	}
	int build(int start, int end){
		if(start==end){
			Node tmp(inf);
			luu.push_back(tmp);
			return luu.size()-1;
		}else{
			int mid = (start+end)/2;
			Node tmp(inf);
			int t = build(start, mid);
			int p = build(mid+1, end);
			tmp.l = t, tmp.r = p;
			luu.push_back(tmp);
			return luu.size()-1;
		}
	}
	
	int update(int start, int end, int p, int x, int id){
		if(start==end){
			Node tmp(0);
			tmp.val = luu[id].val;
			tmp.val = max(tmp.val, x);
			luu.push_back(tmp);
			return luu.size()-1;
		}else{
			int mid = (start+end)/2;
			Node tmp(0);
			tmp.val = luu[id].val;
			tmp.l = luu[id].l, tmp.r = luu[id].r;
			if(p<=mid){
				int tr = update(start, mid, p, x, luu[id].l);
				tmp.l = tr;
			}else{
				int tr = update(mid+1, end, p, x, luu[id].r);
				tmp.r = tr;
			}
			tmp.val = max(luu[tmp.l].val, luu[tmp.r].val);
			luu.push_back(tmp);
			return luu.size()-1;
		}
	}
	
	int query(int start, int end, int l, int r, int id){
		if(start > r or end<l)return inf;
		if(l<=start and end<=r){
			return luu[id].val;
		}
		int mid = (start+end)/2;
		return max(query(start, mid, l, r, luu[id].l), query(mid+1,end, l, r, luu[id].r));
	}
};

pst cay[300005];
vector<int> seg[300005];
vector<int> pf[300005], lz[300005]; //X
void merge(vector<int> &a, vector<int> &b, vector<int> &c, int node){
	int i = 1, j = 1;
	while(i<a.size() and j<b.size()){
		if(a[i] < b[j]){
			c.push_back(a[i]);
			trz[node].push_back(trz[2*node][i]);
			pf[node].push_back(pf[2*node][i]);
			i++;
		}else{
			c.push_back(b[j]);
			trz[node].push_back(trz[2*node+1][j]);
			pf[node].push_back(pf[2*node+1][j]);
			j++;
		}
	}
	while(i<a.size()){
		c.push_back(a[i]);
		trz[node].push_back(trz[2*node][i]);
		pf[node].push_back(pf[2*node][i]);
		i++;
	}
	while(j<b.size()){
		c.push_back(b[j]);
		pf[node].push_back(pf[2*node+1][j]);
		trz[node].push_back(trz[2*node+1][j]);
		j++;
	}
	
}

void merge2(vector<int> &a, vector<int> &b, vector<int> &c){
	int i = 1, j = 1;
	while(i<a.size() and j<b.size()){
		if(a[i] < b[j]){
			c.push_back(a[i]);
			i++;
		}else{
			c.push_back(b[j]);
			j++;
		}
	}
	while(i<a.size()){
		c.push_back(a[i]);
		i++;
	}
	while(j<b.size()){
		c.push_back(b[j]);
		j++;
	}
	
}

void reset(){
	for (int i = 1;i<2*n;++i){
		tr[i].clear();
		trz[i].clear();
		luu[i].clear();
		pf[i].clear();
		lz[i].clear();
		seg[i].clear();
		cay[i].clear();
	}
}

void build(){
	for (int i = 1;i<=n;++i){
		tr[i+n-1].push_back(-1);
		trz[i+n-1].push_back(-1);
		luu[i+n-1].push_back(-1);
		pf[i+n-1].push_back(-1);
		lz[i+n-1].push_back(-1);
		pf[i+n-1].push_back(a[i].x);
		tr[i+n-1].push_back(a[i].y);
		luu[i+n-1].push_back(a[i].z);
		trz[i+n-1].push_back(a[i].z);
		lz[i+n-1].push_back(a[i].z);
		int m=tr[i+n-1].size()-1;
		int root = cay[i+n-1].build(1, m);
		seg[i+n-1].push_back(root);
		for (int j = 1;j<=m;++j){
			int p = lower_bound(luu[i+n-1].begin(), luu[i+n-1].end(), trz[i+n-1][j])-luu[i+n-1].begin();
			int nr = cay[i+n-1].update(1, m, p, pf[i+n-1][j], seg[i+n-1].back());
			seg[i+n-1].push_back(nr);
		}
	}
	for (int i = n-1;i>=1;--i){
		tr[i].push_back(-1);
		trz[i].push_back(-1);
		luu[i].push_back(-1);
		pf[i].push_back(-1);
		lz[i].push_back(-1);
		merge(tr[2*i], tr[2*i+1], tr[i], i);
		merge2(luu[2*i], luu[2*i+1], luu[i]);
		int m=tr[i].size()-1;
		int root = cay[i].build(1, m);
		seg[i].push_back(root);
		for (int j = 1;j<=m;++j){
			int p = lower_bound(luu[i].begin(), luu[i].end(), trz[i][j])-luu[i].begin();
			int nr = cay[i].update(1, m, p, pf[i][j], seg[i].back());
			seg[i].push_back(nr);
		}
		for (int j = 1;j<=m;++j){
			lz[i].push_back(trz[i][j]);
			lz[i][j] = max(lz[i][j], lz[i][j-1]);
		}
	}
}

int q1(int l, int r, int y){
	l = l+n-1, r = r+n-1;
	int res = -1;
	while(l<=r){
		if(l&1){
			int p = lower_bound(tr[l].begin(), tr[l].end(), y)-tr[l].begin()-1;
			res = max (res, lz[l][p]);
			l++;
		}
		if(!(r&1)){
			int p = lower_bound(tr[r].begin(), tr[r].end(), y)-tr[r].begin()-1;
			res = max (res, lz[r][p]);
			r--;
		}
		l/=2;
		r/=2;
	}
	return res;
}

int q2(int l, int r, int y, int z){
	l = l+n-1, r = r+n-1;
	int res = inf;
	while(l<=r){
		if(l&1){
			int p = lower_bound(tr[l].begin(), tr[l].end(), y)-tr[l].begin()-1;
			int m = tr[l].size()-1;
			int q = lower_bound(luu[l].begin(), luu[l].end(), z)-luu[l].begin()-1;
			int sol = cay[l].query(1, m, 1, q, seg[l][p]);
			res = max(res, sol);
			l++;
		}
		if(!(r&1)){
			int p = lower_bound(tr[r].begin(), tr[r].end(), y)-tr[r].begin()-1;
			int m = tr[r].size()-1;
			int q = lower_bound(luu[r].begin(), luu[r].end(), z)-luu[r].begin()-1;
			int sol = cay[r].query(1, m, 1, q, seg[r][p]);
			res = max(res, sol);
			r--;
		}
		l/=2;
		r/=2;
	}
	return res;
}

signed main(){
	// ios_base::sync_with_stdio(0);
	// cin.tie(0);
	// freopen("team_contest.inp","r",stdin);
	// freopen("team_contest.out","w",stdout);
	init_output();
	// cin >> n;
	n = read_ll();
	for (int i = 1;i<=n;++i){
		// cin >> a[i].x >> a[i].y >> a[i].z;
		a[i].x = read_ll();
		a[i].y = read_ll();
		a[i].z = read_ll();
	}
	sort(a+1, a+n+1, [](mem p, mem q){
		return p.x < q.x;
	});
	int tro = 1;
	// return 0;
	build();
	// return 0;
	int res = -1;
	for (int i = 2;i<=n;++i){
		while(tro<=n and a[tro].x<=a[i].x){
			tro++;
		}
		int mz = q1(1, i-1, a[i].y);
		if(mz > a[i].z){
			int sol = q2(tro, n, a[i].y, mz);
			if(sol!=inf){
				res = max(res, a[i].y + mz + sol);
			}
		}
	}
	// return 0;
	// cout << res << '\n';
	reset();
	for (int i = 1;i<=n;++i){
		swap(a[i].y, a[i].z);
	}
	tro = 1;
	build();
	// return 0;
	// int res = 0;
	for (int i = 2;i<=n;++i){
		while(tro<=n and a[tro].x<=a[i].x){
			tro++;
		}
		int mz = q1(1, i-1, a[i].y);
		if(mz > a[i].z){
			int sol = q2(tro, n, a[i].y, mz);
			if(sol!=inf){
				res = max(res, a[i].y + mz + sol);
				// cout << res << ' ' << mz << ' ' << i << '\n';
			}
		}
	}
	write_ll(res);
}

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