Submission #549430

#	Time	Username	Problem	Language	Result	Execution time	Memory
549430		keta_tsimakuridze	Team Contest (JOI22_team)	C++14	100 / 100	1638 ms	271120 KiB

team

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

#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"

const int N = 5e5 + 5, mod = 1e9 + 7, inf = 1e9; //!
int t, tree[4 * N][2], cur, val[N], rr2[N][2];
pair<int,pii> p[N];
set<pii> s[4 * N][2];
void upd(int u, int id, int l,int r,int t,int val) {
	if(l > id || r < id) return;
	if(l == r) {
		tree[u][t] = max(tree[u][t], val);
		return;
	}
	int mid = (l + r) / 2;
	upd(2 * u, id, l, mid, t, val); upd(2 * u + 1, id, mid + 1,r, t, val);
	for(int k = 0; k < 2; k++) tree[u][k] = max(tree[2 * u][k], tree[2 * u + 1][k]);
}
int get(int u,int st,int en,int l,int r,int t) {
	if(l > en || r < st) return 0;
	if(st <= l && r <= en) return tree[u][t];
	int mid = (l + r) / 2;
	return max(get(2 * u, st, en, l, mid, t), get(2 * u + 1, st, en, mid + 1, r, t));
}

void updSum(int u,int id, int l,int r, int t, int val1, int val2) {
	if(l > id || r < id) return;
	int f = 0;
	if(s[u][t].size() && s[u][t].upper_bound({val1, 0}) != s[u][t].end() ) {
		if((*s[u][t].upper_bound({val1, 0})).s >= val1 + val2)f = 1;
		else 			
		if((*s[u][t].upper_bound({val1, 0})).f == val1) {
				s[u][t].erase((*s[u][t].upper_bound({val1, 0})));
		}
	}
	if(!f) s[u][t].insert({val1, val2 + val1});
	while(!f && s[u][t].size() && s[u][t].upper_bound({val1 - 1, inf}) != s[u][t].begin()) {
		pii p = *--s[u][t].upper_bound({val1 - 1, inf});
		if(p.s > val1 + val2) break;
		s[u][t].erase(p);
	}
	for(set<pii> :: iterator it = s[u][t].begin(); it != s[u][t].end(); it++) {
		if((*it).f < val1 && (*it).s <= val1 + val2) {
			s[u][t].erase(*it);
			it--;
		}
	}
	if(l == r) return;
	int mid = (l + r) / 2;
	updSum(2 * u, id, l, mid, t, val1, val2); updSum(2 * u + 1, id, mid + 1,r, t, val1, val2);
}
int getSum(int u,int st, int en, int l,int r,int t,int val1) {
	if(l > en || r < st) return -inf;
	if(st <= l && r <= en) {
		if(s[u][t].upper_bound({val1 + 1, 0}) == s[u][t].end()) return -inf;
		return (*s[u][t].upper_bound({val1 + 1, 0})).s;
	}
	int mid = (l + r) / 2;
	return max(getSum(2 * u, st, en, l, mid, t, val1), getSum(2 * u + 1, st, en, mid + 1, r, t, val1));
}
void add(pair<int, pii> p) {
	int a = p.s.f, b = p.s.s;
	int mxa = get(1, 1, a - 1, 1, cur, 0); 
	int mxb = get(1, 1, b - 1, 1, cur, 1); 
	upd(1, a, 1, cur, 0, b);
	upd(1, b, 1, cur, 1, a);
	if(mxa <= b) mxa = 0; if(mxb <= a) mxb = 0;
//	rr2[a][0] = max(rr2[a][0], mxa);
//	rr2[b][1] = max(rr2[b][1], mxb);
	if(mxa)
	updSum(1, a, 1, cur, 0, val[mxa], val[a]); 
	if(mxb)
	updSum(1, b, 1, cur, 1, val[mxb], val[b]);
}
int getSum2(int u,int st, int en, int l,int r,int t,int val1) {
	int ans = -inf;
	for(int i = st; i <= en; i++) {
		if(val1 < val[rr2[i][t]]) 
		ans = max(ans, val[rr2[i][t]] + val[i]);
	}
	return ans;
}
main() {
	ios_base::sync_with_stdio(false),
	cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	vector<int> x;
	map<int,int> id;
	for(int i = 1; i <= n; i++) {
		cin >> p[i].f >> p[i].s.f >> p[i].s.s;
		x.push_back(p[i].f); x.push_back(p[i].s.f); x.push_back(p[i].s.s);
	}
	sort(x.begin(),x.end());
	cur = 0;
	for(int i = 0; i < x.size(); i++) {
		if(!i || x[i] != x[i - 1]) ++cur;
		id[x[i]] = cur;
		val[cur] = x[i];
	}
	for(int i = 1; i <= n; i++) {
		p[i].f = id[p[i].f];
		p[i].s.f = id[p[i].s.f];
		p[i].s.s = id[p[i].s.s];
	}
	val[0] = -inf;
	sort(p + 1, p + n + 1);
	int last = 0, ans = -inf;
	for(int i = 1; i <= n; i++) {
		
		int x = 0;
		
		x = max(getSum(1, p[i].s.s + 1, cur, 1, cur, 1, val[p[i].s.f]), getSum(1, p[i].s.f + 1, cur, 1, cur, 0, val[p[i].s.s]));
		ans = max(ans, x + val[p[i].f]);
		if(p[i].f != p[i + 1].f) {
			for(int j = last + 1; j <= i; j++) {

				add(p[j]);
			}
			last = i;
		}
	}
	ans = max(ans, -1);
	cout << ans;
}

Compilation message (stderr)

team.cpp: In function 'void add(std::pair<int, std::pair<int, int> >)':
team.cpp:71:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   71 |  if(mxa <= b) mxa = 0; if(mxb <= a) mxb = 0;
      |  ^~
team.cpp:71:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   71 |  if(mxa <= b) mxa = 0; if(mxb <= a) mxb = 0;
      |                        ^~
team.cpp: At global scope:
team.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main() {
      | ^~~~
team.cpp: In function 'int main()':
team.cpp:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~

• 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