Submission #887476

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
887476	2023-12-14T15:28:00 Z	Ahmed57	Team Contest (JOI22_team)	C++17	0 / 100	43 ms	7884 KB

team

#include <bits/stdc++.h>
using namespace std;
#define int long long
int seg1[1800001],seg2[1800001];
void build(int p,int l,int r){
	seg1[p] = seg2[p] = -1e9;
    if(l==r){
        return ;
    }
    int md = (l+r)/2;
    build(p*2,l,md);build(p*2+1,md+1,r);
}
void update1(int p,int l,int r,int idx,int val){
	if(l==r){
		seg1[p] = max(seg1[p],val);
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update1(p*2,l,md,idx,val);
	else update1(p*2+1,md+1,r,idx,val);
	seg1[p] = max(seg1[p*2],seg1[p*2+1]);
}void update2(int p,int l,int r,int idx,int val){
	if(l==r){
		seg2[p] = max(seg2[p],val);
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update2(p*2,l,md,idx,val);
	else update2(p*2+1,md+1,r,idx,val);
	seg2[p] = max(seg2[p*2],seg2[p*2+1]);
}
int query1(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq)return seg1[p];
    int md = (l+r)/2;
    return max(query1(p*2,l,md,lq,rq),query1(p*2+1,md+1,r,lq,rq));
}int query2(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e9;
    if(l>=lq&&r<=rq)return seg2[p];
    int md = (l+r)/2;
    return max(query2(p*2,l,md,lq,rq),query2(p*2+1,md+1,r,lq,rq));
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	int n;
	cin>>n;
	vector<array<int,3>> v;
	map<int,int> mp,sav;
	for(int i = 0;i<n;i++){
		int a,b,c;cin>>a>>b>>c;
		v.push_back({a,b,c});
		mp[a]++;
		mp[b]++;
		mp[c]++;
	}
	int cnt = 0;
	for(auto i:mp){
		sav[i.first] = ++cnt;
	}
	sort(v.begin(),v.end());
	int ind = 0;
	long long all = -1e9 , ans = -1e9;
	build(1,1,cnt);
	for(int i = 0;i<n;i++){
        while(v[ind][0]<v[i][0]){
            {//taking first as max
                long long val = query1(1,1,cnt,1,v[ind][1]-1);
                if(val>v[ind][2]){
                	all = max(all,v[ind][1]+val);
                }
            }
            {
                long long val = query2(1,1,cnt,1,v[ind][2]-1);
                if(val>v[ind][1]){
                	all = max(all,v[ind][2]+val);
                }
            }
            update1(1,1,cnt,sav[v[ind][1]],v[ind][2]);
            update2(1,1,cnt,sav[v[ind][2]],v[ind][1]);
            ind++;
        }
        ans = max(ans,all+v[i][0]);
	}
	cout<<(ans<0?-1:ans)<<endl;
}

Subtask #1
0 / 8.0

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

Subtask #2
0 / 29.0

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

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	43 ms	7884 KB	Output is correct
12	Incorrect	28 ms	5056 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	43 ms	7884 KB	Output is correct
12	Incorrect	28 ms	5056 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	43 ms	7884 KB	Output is correct
12	Incorrect	28 ms	5056 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	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2648 KB	Output is correct
4	Correct	0 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	2396 KB	Output is correct
10	Correct	1 ms	2396 KB	Output is correct
11	Correct	43 ms	7884 KB	Output is correct
12	Incorrect	28 ms	5056 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #7
0 / 27.0

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

Submission #887476

Compilation message

Subtask #1 0 / 8.0

Subtask #2 0 / 29.0

Subtask #3 0 / 9.0

Subtask #4 0 / 9.0

Subtask #5 0 / 9.0

Subtask #6 0 / 9.0

Subtask #7 0 / 27.0

Subtask #1
0 / 8.0

Subtask #2
0 / 29.0

Subtask #3
0 / 9.0

Subtask #4
0 / 9.0

Subtask #5
0 / 9.0

Subtask #6
0 / 9.0

Subtask #7
0 / 27.0