Submission #547743

#	Time	Username	Problem	Language	Result	Execution time	Memory
547743		Pherokung	Team Contest (JOI22_team)	C++14	0 / 100	581 ms	39804 KiB

team

#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
typedef pair<int,int> pa;
int n,val[150005][3],rev_val[150005][3],ind_val[150005][3],cnt;
map<int,int> hsh;
vector<pa> srt_val[3];
vector<int> A[150005];

struct node{
	int val,mx;
	node *l,*r;
};
node top, top2, top3;

void build(node *pos,int be,int ed){
	if(be == ed){
		pos->val = 0, pos->mx = 0;
		return;
	}
	int mid = (be+ed)/2;
	pos->l = new node, pos->r = new node;
	build(pos->l,be,mid), build(pos->r,mid+1,ed);
	pos->val = 0, pos->mx = 0;
}

void update(node *pos,int be,int ed,int x,int v){
	if(be > ed || x < be || ed < x) return;
	if(be == ed){
		if(v > pos->mx){
			pos->val = rev_val[be][1] + rev_val[v][2];
//			printf("?? %d %d : %d %d\n",be,v,rev_val[be][1],rev_val[v][2]);
			pos->mx = v;	
		}
		return;	
	}
	int mid = (be+ed)/2;
	update(pos->l,be,mid,x,v);
	update(pos->r,mid+1,ed,x,v);
	pos->val = max(pos->l->val,pos->r->val), pos->mx = max(pos->l->mx,pos->r->mx);
}

pa query(node *pos,int be,int ed,int x,int y){
	if(be > ed || y < be || ed < x) return {0,0};
	if(x <= be && ed <= y) return {pos->val,pos->mx};
	int mid = (be+ed)/2;
	pa X = query(pos->l,be,mid,x,y), Y = query(pos->r,mid+1,ed,x,y);
	return {max(X.F,Y.F), max(X.S,Y.S)};
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=0;j<=2;j++){
			scanf("%d",&val[i][j]);
			srt_val[j].push_back({val[i][j],i});
		}
	}
	
	for(int i=0;i<=2;i++){
		sort(srt_val[i].begin(),srt_val[i].end());
		hsh.clear();
		cnt = 1;
		for(auto x : srt_val[i]){
			if(hsh[x.F] == 0) hsh[x.F] = cnt++;
			ind_val[x.S][i] = hsh[x.F];
			rev_val[hsh[x.F]][i] = x.F; 
		}
	}
	
	build(&top,1,n);
	build(&top2,1,n);
	build(&top3,1,n);
	for(int i=1;i<=n;i++) A[ind_val[i][0]].push_back(i);
	int ans = -1;
	
	for(int i=1;i<=n;i++){
		for(auto x : A[i]){
			int ind = x, a = i, b = ind_val[ind][1], c = ind_val[ind][2];
			int be = b+1, ed = n;
			while(be<ed){
				int mid = (be+ed)/2;
				if(query(&top,1,n,mid,n).S >= c) be = mid+1;
				else ed = mid;
			}
//			printf("\n=============\n");
//			for(int i=1;i<=n;i++) printf("%d ",query(&top,1,n,i,i).F);
//			printf("\n=============\n");
//			printf("!! %d %d %d >> %d %d\n",a,b,c,ed,query(&top,1,n,1,ed).F);
			int vv = query(&top,1,n,1,ed).F;
			if(vv != 0) ans = max(ans,val[ind][0] + vv);
		}
		for(auto x : A[i]){
			int ind = x, a = i, b = ind_val[ind][1], c = ind_val[ind][2];
			int mx_c = query(&top2,1,n,1,b-1).S, mx_b = query(&top3,1,n,1,c-1).S;
//			printf("|| %d : %d %d %d >> %d %d\n",ind,a,b,c,mx_c,mx_b);
			if(mx_c > c) update(&top,1,n,b,mx_c);
			update(&top2,1,n,b,c);
			if(mx_b > b) update(&top,1,n,mx_b,c);
			update(&top3,1,n,c,b);
		}
	}
	
	printf("%d",ans);
}

Compilation message (stderr)

team.cpp: In function 'int main()':
team.cpp:80:17: warning: unused variable 'a' [-Wunused-variable]
   80 |    int ind = x, a = i, b = ind_val[ind][1], c = ind_val[ind][2];
      |                 ^
team.cpp:95:17: warning: unused variable 'a' [-Wunused-variable]
   95 |    int ind = x, a = i, b = ind_val[ind][1], c = ind_val[ind][2];
      |                 ^
team.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
team.cpp:56:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |    scanf("%d",&val[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~

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