Submission #545330

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
545330	2022-04-04T09:23:27 Z	Meloric	Team Contest (JOI22_team)	C++14	0 / 100	2000 ms	6596 KB

team

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf  = 1e18;

struct triple{
	int x, y, z;
	void p(){
		cout << x << ' '<< y << ' '<< z << '\n';
	}
};

void solve(){
	int n; cin >> n;
	vector<triple>A;
	for(int i = 0; i< n; i++){
		int x, y, z; cin >> x >> y >> z;
		A.pb({x, y, z});
	}
	sort(all(A), [](const triple& a, const triple& b){return a.z < b.z;});
	int by = -1;
	int bx = -1;
	int ans = -1;
	
	set<pii> S;
	
	for(int i = 0; i< n;){
		deque<triple> q;
		for(; i< n && (q.empty() || q.back().z == A[i].z); i++)q.pb(A[i]);
		for(auto& e : q){
			int x = e.x;
			int y = e.y;
			int z = e.z;
			
			if(by != -1 && bx != -1 && by > y && bx > x)ans = by+bx+z;
		}
		for(auto& e : q){
			int x = e.x;
			int y = e.y;
			
			if(x <= bx && y <= by)continue;
			if(x > bx && y < by)bx = x;
			if(x < bx && y > by)by = y;

			auto it = S.lb({x, -inf});
			if(it != S.begin()){
				it--;
				if((*it).Y > y){
					bx = x;
					by = (*it).Y;
				}
			}
			it = S.lb({x, inf});
			if(it != S.end()){
				while(next(it) != S.end() && (*next(it)).Y < y)it++;
				bx = (*it).X;
				by = y;
			}
			S.insert({x, y});
			while(S.size() && (*S.begin()).X <= bx || (*S.begin()).Y <= by)S.erase(S.begin());
		}
	}
	cout << ans;
}

	
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}

Compilation message

team.cpp: In function 'void solve()':
team.cpp:69:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   69 |    while(S.size() && (*S.begin()).X <= bx || (*S.begin()).Y <= by)S.erase(S.begin());
      |          ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Execution timed out	2082 ms	340 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #2

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Execution timed out	2082 ms	340 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-

Subtask #3

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	260 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	30 ms	6596 KB	Output is correct
12	Incorrect	19 ms	3528 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #4

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	260 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	30 ms	6596 KB	Output is correct
12	Incorrect	19 ms	3528 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #5

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	260 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	30 ms	6596 KB	Output is correct
12	Incorrect	19 ms	3528 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #6

0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	260 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	30 ms	6596 KB	Output is correct
12	Incorrect	19 ms	3528 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	1 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	0 ms	212 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	0 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Execution timed out	2082 ms	340 KB	Time limit exceeded
15	Halted	0 ms	0 KB	-