oj.uz

Submission #547743

# Submission time Handle Problem Language Result Execution time Memory
547743 2022-04-11T14:52:33 Z Pherokung Team Contest (JOI22_team) C++14
0 / 100
 581 ms 39804 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 3 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 2 ms 3796 KB Output is correct
13 Correct 2 ms 3808 KB Output is correct
14 Correct 2 ms 3924 KB Output is correct
15 Incorrect 2 ms 3796 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 3 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 2 ms 3796 KB Output is correct
13 Correct 2 ms 3808 KB Output is correct
14 Correct 2 ms 3924 KB Output is correct
15 Incorrect 2 ms 3796 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3828 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 581 ms 39804 KB Output is correct
12 Incorrect 355 ms 27916 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3828 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 581 ms 39804 KB Output is correct
12 Incorrect 355 ms 27916 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3828 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 581 ms 39804 KB Output is correct
12 Incorrect 355 ms 27916 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 2 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 2 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 2 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3828 KB Output is correct
10 Correct 3 ms 3796 KB Output is correct
11 Correct 581 ms 39804 KB Output is correct
12 Incorrect 355 ms 27916 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3796 KB Output is correct
2 Correct 3 ms 3796 KB Output is correct
3 Correct 2 ms 3796 KB Output is correct
4 Correct 3 ms 3796 KB Output is correct
5 Correct 2 ms 3796 KB Output is correct
6 Correct 3 ms 3796 KB Output is correct
7 Correct 3 ms 3796 KB Output is correct
8 Correct 2 ms 3796 KB Output is correct
9 Correct 2 ms 3796 KB Output is correct
10 Correct 2 ms 3796 KB Output is correct
11 Correct 2 ms 3796 KB Output is correct
12 Correct 2 ms 3796 KB Output is correct
13 Correct 2 ms 3808 KB Output is correct
14 Correct 2 ms 3924 KB Output is correct
15 Incorrect 2 ms 3796 KB Output isn't correct
16 Halted 0 ms 0 KB -