Submission #972512

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
972512	2024-04-30T14:09:09 Z	happy_node	Team Contest (JOI22_team)	C++17	0 / 100	210 ms	34748 KB

team

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MX=2e5+5;
int N;
int X[MX],Y[MX],Z[MX],mn[MX];

vector<pair<int,int>> ops[MX];

priority_queue<int, vector<int>, greater<int>> pend[MX]; 

struct segtree {
    	pair<int,int> t[4 * MX];
 
     	void update(int v, int l, int r, int pos, int val) {
           	if(l > pos || r < pos) return;
           	if(l == r) {
                 	t[v] = make_pair(val, pos);
                 	return;
           	}
           	int mid = (l + r) >> 1;
           	update(v * 2 + 0, l, mid + 0, pos, val);
           	update(v * 2 + 1, mid + 1, r, pos, val);
           	t[v] = min(t[v * 2 + 0], t[v * 2 + 1]);
     	}
 
     	pair<int,int> query(int v, int l, int r, int ql, int qr) {
           	if(ql > r || qr < l) return make_pair(1e9, 1e9);
           	if(ql <= l && qr >= r) return t[v];
           	int mid = (l + r) >> 1;
           	return min(query(v * 2 + 0, l, mid + 0, ql, qr), query(v * 2 + 1, mid + 1, r, ql, qr));
      	}

      	void prep() {
      		for(int i=0;i<4*MX;i++) t[i]=make_pair(1e9,i);
      	}
} st, tt;

priority_queue<pair<int,int>> pts;

ll rx[MX], ry[MX], rz[MX];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	st.prep();
	tt.prep();

	cin>>N;

	map<int,int> ix,iy,iz;
	for(int i=0;i<N;i++) {
		cin>>X[i]>>Y[i]>>Z[i];
		ix[X[i]]=0;
		iy[Y[i]]=0;
		iz[Z[i]]=0;
	}

	int p=0;
	for(auto &[x,y]:ix) y=p++, rx[y]=x;
	p=0;
	for(auto &[x,y]:iy) y=p++, ry[y]=x;
	p=0;
	for(auto &[x,y]:iz) y=p++, rz[y]=x;

	for(int i=0;i<N;i++) {
		ops[iz[Z[i]]].push_back({ix[X[i]],iy[Y[i]]});
		pend[i].push(1e9);
		mn[i]=1e9;
	} 	

	ll ans=-1;

	for(int z=0;z<N;z++) {
		// evaluate
		for(auto [x,y]:ops[z]) {
			if(pts.empty()) continue;
			auto [yy,xx]=pts.top();

			// wanna get rightmost x
			int l=0,r=N,res=-1;
			while(l<=r) {
				int mid=(l+r)/2;
				if(tt.query(1,0,N,mid,N).first<yy) {
					res=mid,l=mid+1;
				} else {
					r=mid-1;
				}
			}
			if(res<=x||yy<=y) continue;

			ans=max(ans,rz[z]+ry[yy]+rx[res]);
		}	

		// insert
		for(auto [x,y]:ops[z]) {
			if(tt.query(1,0,N,x,N).first>=y) {
				pend[y].push(x);
				st.update(1,0,N,y,pend[y].top());
			} else {
				pts.push({y,x});
			}
			mn[x]=min(mn[x],y);
			tt.update(1,0,N,x,mn[x]);
		}

		for(auto [x,y]:ops[z]) {
			while(true) {
				auto [v,k]=st.query(1,0,N,y+1,N);
				if(v<x) {
					pts.push({k,v});
					pend[k].pop();
					st.update(1,0,N,k,pend[k].top());
				} else {
					break;
				}
			}
		}
	}

	cout<<ans<<'\n';
}

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	29016 KB	Output is correct
2	Correct	6 ms	26972 KB	Output is correct
3	Correct	7 ms	27160 KB	Output is correct
4	Correct	6 ms	24924 KB	Output is correct
5	Correct	5 ms	25072 KB	Output is correct
6	Correct	5 ms	24924 KB	Output is correct
7	Correct	5 ms	24924 KB	Output is correct
8	Correct	6 ms	24924 KB	Output is correct
9	Correct	6 ms	24972 KB	Output is correct
10	Correct	6 ms	24924 KB	Output is correct
11	Correct	6 ms	24924 KB	Output is correct
12	Correct	7 ms	24920 KB	Output is correct
13	Correct	7 ms	24924 KB	Output is correct
14	Correct	8 ms	25180 KB	Output is correct
15	Incorrect	8 ms	24924 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #2

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	29016 KB	Output is correct
2	Correct	6 ms	26972 KB	Output is correct
3	Correct	7 ms	27160 KB	Output is correct
4	Correct	6 ms	24924 KB	Output is correct
5	Correct	5 ms	25072 KB	Output is correct
6	Correct	5 ms	24924 KB	Output is correct
7	Correct	5 ms	24924 KB	Output is correct
8	Correct	6 ms	24924 KB	Output is correct
9	Correct	6 ms	24972 KB	Output is correct
10	Correct	6 ms	24924 KB	Output is correct
11	Correct	6 ms	24924 KB	Output is correct
12	Correct	7 ms	24920 KB	Output is correct
13	Correct	7 ms	24924 KB	Output is correct
14	Correct	8 ms	25180 KB	Output is correct
15	Incorrect	8 ms	24924 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #3

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	24924 KB	Output is correct
2	Correct	8 ms	24920 KB	Output is correct
3	Correct	8 ms	25084 KB	Output is correct
4	Correct	7 ms	24920 KB	Output is correct
5	Correct	7 ms	24924 KB	Output is correct
6	Correct	9 ms	24924 KB	Output is correct
7	Correct	9 ms	24920 KB	Output is correct
8	Correct	8 ms	24924 KB	Output is correct
9	Correct	7 ms	25376 KB	Output is correct
10	Correct	7 ms	24924 KB	Output is correct
11	Correct	210 ms	34748 KB	Output is correct
12	Incorrect	142 ms	32128 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	24924 KB	Output is correct
2	Correct	8 ms	24920 KB	Output is correct
3	Correct	8 ms	25084 KB	Output is correct
4	Correct	7 ms	24920 KB	Output is correct
5	Correct	7 ms	24924 KB	Output is correct
6	Correct	9 ms	24924 KB	Output is correct
7	Correct	9 ms	24920 KB	Output is correct
8	Correct	8 ms	24924 KB	Output is correct
9	Correct	7 ms	25376 KB	Output is correct
10	Correct	7 ms	24924 KB	Output is correct
11	Correct	210 ms	34748 KB	Output is correct
12	Incorrect	142 ms	32128 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	24924 KB	Output is correct
2	Correct	8 ms	24920 KB	Output is correct
3	Correct	8 ms	25084 KB	Output is correct
4	Correct	7 ms	24920 KB	Output is correct
5	Correct	7 ms	24924 KB	Output is correct
6	Correct	9 ms	24924 KB	Output is correct
7	Correct	9 ms	24920 KB	Output is correct
8	Correct	8 ms	24924 KB	Output is correct
9	Correct	7 ms	25376 KB	Output is correct
10	Correct	7 ms	24924 KB	Output is correct
11	Correct	210 ms	34748 KB	Output is correct
12	Incorrect	142 ms	32128 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	24924 KB	Output is correct
2	Correct	8 ms	24920 KB	Output is correct
3	Correct	8 ms	25084 KB	Output is correct
4	Correct	7 ms	24920 KB	Output is correct
5	Correct	7 ms	24924 KB	Output is correct
6	Correct	9 ms	24924 KB	Output is correct
7	Correct	9 ms	24920 KB	Output is correct
8	Correct	8 ms	24924 KB	Output is correct
9	Correct	7 ms	25376 KB	Output is correct
10	Correct	7 ms	24924 KB	Output is correct
11	Correct	210 ms	34748 KB	Output is correct
12	Incorrect	142 ms	32128 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	29016 KB	Output is correct
2	Correct	6 ms	26972 KB	Output is correct
3	Correct	7 ms	27160 KB	Output is correct
4	Correct	6 ms	24924 KB	Output is correct
5	Correct	5 ms	25072 KB	Output is correct
6	Correct	5 ms	24924 KB	Output is correct
7	Correct	5 ms	24924 KB	Output is correct
8	Correct	6 ms	24924 KB	Output is correct
9	Correct	6 ms	24972 KB	Output is correct
10	Correct	6 ms	24924 KB	Output is correct
11	Correct	6 ms	24924 KB	Output is correct
12	Correct	7 ms	24920 KB	Output is correct
13	Correct	7 ms	24924 KB	Output is correct
14	Correct	8 ms	25180 KB	Output is correct
15	Incorrect	8 ms	24924 KB	Output isn't correct
16	Halted	0 ms	0 KB	-