oj.uz

Submission #887490

# Submission time Handle Problem Language Result Execution time Memory
887490 2023-12-14T16:04:10 Z Ahmed57 Team Contest (JOI22_team) C++17
18 / 100
 77 ms 11096 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
long long seg1[1800001],seg2[1800001];
pair<long long,long long> seg3[1800001],seg4[1800001];

void build(int p,int l,int r){
	seg1[p] = seg2[p] = -1e18;
	seg3[p] = {-1e18,-1e18};
	seg4[p] = {-1e18,-1e18};
    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,long long 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,long long 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]);
}void update3(int p,int l,int r,int idx,long long val2,long long val){
	if(l==r){
		seg3[p] = max(seg3[p],make_pair(val2+val,val));
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update3(p*2,l,md,idx,val2,val);
	else update3(p*2+1,md+1,r,idx,val2,val);
	seg3[p] = max(seg3[p*2],seg3[p*2+1]);
}void update4(int p,int l,int r,int idx,long long val2,long long val){
	if(l==r){
		seg4[p] = max(seg4[p],make_pair(val2+val,val));
		return ;
	}
	int md = (l+r)/2;
	if(idx<=md)update4(p*2,l,md,idx,val2,val);
	else update4(p*2+1,md+1,r,idx,val2,val);
	seg4[p] = max(seg4[p*2],seg4[p*2+1]);
}
long long query1(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e18;
    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));
}long long query2(int p,int l,int r,int lq,int rq){
	if(r<lq||l>rq||lq>rq)return -1e18;
    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));
}long long query3(int p,int l,int r,int lq,int rq,int limit){
	if(r<lq||l>rq||lq>rq)return -1e18;
    if(l>=lq&&r<=rq){
    	if(seg3[p].second>limit)return seg3[p].first;
    	else return -1e18;
    }
    int md = (l+r)/2;
    return max(query3(p*2,l,md,lq,rq,limit),query3(p*2+1,md+1,r,lq,rq,limit));
}long long query4(int p,int l,int r,int lq,int rq,int limit){
	if(r<lq||l>rq||lq>rq)return -1e18;
    if(l>=lq&&r<=rq){
    	if(seg4[p].second>limit)return seg4[p].first;
    	else return -1e18;
    }
    int md = (l+r)/2;
    return max(query4(p*2,l,md,lq,rq,limit),query4(p*2+1,md+1,r,lq,rq,limit));
}
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 = -1e18 , ans = -1e18;
	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]){
                	update3(1,1,cnt,sav[v[ind][1]],v[ind][1],val);
                }
            }
            {
                long long val = query2(1,1,cnt,1,v[ind][2]-1);
                if(val>v[ind][1]){
                	update4(1,1,cnt,sav[v[ind][2]],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,v[i][0]+max(query3(1,1,cnt,sav[v[i][1]]+1,cnt,v[i][2]),query4(1,1,cnt,sav[v[i][2]]+1,cnt,v[i][1])));
	}
	cout<<(ans<0?-1:ans)<<endl;
}

Compilation message

team.cpp: In function 'int main()':
team.cpp:102:12: warning: unused variable 'all' [-Wunused-variable]
  102 |  long long all = -1e18 , ans = -1e18;
      |            ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Incorrect 1 ms 6492 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 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6492 KB Output is correct
12 Correct 1 ms 6492 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 2 ms 6748 KB Output is correct
15 Incorrect 1 ms 6492 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 52 ms 11096 KB Output is correct
12 Correct 33 ms 8896 KB Output is correct
13 Correct 35 ms 9640 KB Output is correct
14 Correct 48 ms 10680 KB Output is correct
15 Correct 39 ms 10688 KB Output is correct
16 Correct 31 ms 10592 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 52 ms 11096 KB Output is correct
12 Correct 33 ms 8896 KB Output is correct
13 Correct 35 ms 9640 KB Output is correct
14 Correct 48 ms 10680 KB Output is correct
15 Correct 39 ms 10688 KB Output is correct
16 Correct 31 ms 10592 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 77 ms 10796 KB Output is correct
23 Correct 69 ms 10960 KB Output is correct
24 Correct 49 ms 9112 KB Output is correct
25 Correct 67 ms 10384 KB Output is correct
26 Correct 42 ms 10444 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 52 ms 11096 KB Output is correct
12 Correct 33 ms 8896 KB Output is correct
13 Correct 35 ms 9640 KB Output is correct
14 Correct 48 ms 10680 KB Output is correct
15 Correct 39 ms 10688 KB Output is correct
16 Correct 31 ms 10592 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 77 ms 10796 KB Output is correct
23 Correct 69 ms 10960 KB Output is correct
24 Correct 49 ms 9112 KB Output is correct
25 Correct 67 ms 10384 KB Output is correct
26 Correct 42 ms 10444 KB Output is correct
27 Incorrect 2 ms 6492 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 52 ms 11096 KB Output is correct
12 Correct 33 ms 8896 KB Output is correct
13 Correct 35 ms 9640 KB Output is correct
14 Correct 48 ms 10680 KB Output is correct
15 Correct 39 ms 10688 KB Output is correct
16 Correct 31 ms 10592 KB Output is correct
17 Correct 1 ms 6492 KB Output is correct
18 Correct 1 ms 6492 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 2 ms 6492 KB Output is correct
22 Correct 77 ms 10796 KB Output is correct
23 Correct 69 ms 10960 KB Output is correct
24 Correct 49 ms 9112 KB Output is correct
25 Correct 67 ms 10384 KB Output is correct
26 Correct 42 ms 10444 KB Output is correct
27 Incorrect 2 ms 6492 KB Output isn't correct
28 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

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