oj.uz

Submission #917743

# Submission time Handle Problem Language Result Execution time Memory
917743 2024-01-28T17:08:44 Z _VIBE Team Contest (JOI22_team) C++17
0 / 100
 97 ms 14720 KB 
#include "bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
typedef tree<pair<int,int>, null_type,less<pair<int,int>>, rb_tree_tag,tree_order_statistics_node_update>ordered_multiset;

#define endl '\n'
#define int long long
const int inf=1ll<<60;

void Excuse_Me(int TC)
{
   
   int n;
   cin>>n;
   
   vector<vector<int>> g(n);
   
   vector<int> v;
   
   for(int i=0;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[i]={a,b,c};
        v.push_back(b);
        v.push_back(b-1);
        v.push_back(b+1);
   }
   
   sort(g.begin(),g.end());
   
   sort(v.begin(),v.end());
   
   v.resize(unique(v.begin(),v.end())-v.begin());
   
   int m=v.size();
   
   map<int,int> comp;
   
   for(int i=0;i<v.size();i++) comp[v[i]]=i;
   
   int mn[4*m],mx[4*m];
   int t[4*m];
   
  
   
   function<void(int,int,int)> build=[&](int s,int e,int i)->void{
        if(s==e){
            mn[i]=inf;
            mx[i]=-inf;
            t[i]=-inf;
            return;
        }
        
        int m=(s+e)/2;
        
        build(s,m,i*2);
        build(m+1,e,i*2+1);
        
        mn[i]=min(mn[i*2],mn[i*2+1]);
        mx[i]=max(mx[i*2],mx[i*2+1]);
        t[i]=-inf;
        
   }; 
   
   
   
   build(0,m-1,1);
   
   vector<pair<int,int>> p;
   
   int ans=-1;
   
   function<void(int,int,int,int,int)> update=[&](int s,int e,int i,int pos,int val)->void{
        if(s==e){
            mn[i]=min(mn[i],val);
            mx[i]=max(mx[i],val);
            return;
        }
        
        int m=(s+e)/2;
        if(pos<=m) update(s,m,i*2,pos,val);
        else update(m+1,e,i*2+1,pos,val);   
        mn[i]=min(mn[i*2],mn[i*2+1]);
        mx[i]=max(mx[i*2],mx[i*2+1]);       
        
   };
   
   function<int(int,int,int,int,int,bool)> get=[&](int s,int e,int i,int l,int r,bool ismax)->int{
        if(l>r) return (ismax?(-inf):(inf));
        
        if(s==l and r==e) return (ismax?mx[i]:mn[i]);
        
        int m=(s+e)/2;
        
        if(ismax) return max(get(s,m,i*2,l,min(m,r),ismax),get(m+1,e,i*2+1,max(m+1,l),r,ismax));
        return min(get(s,m,i*2,l,min(m,r),ismax),get(m+1,e,i*2+1,max(m+1,l),r,ismax));
        
   };
   
   
   ordered_set b_entry;
   
   vector<int> entry(m,-1);
   
   function<int(int,int,int,int,int)> get1=[&](int s,int e,int i,int l,int r)->int{
        
        if(l>r) return -inf;
        
        if(s==l and r==e) return t[i];
        
        int m=(s+e)/2;
        
        return max(get1(s,m,i*2,l,min(m,r)),get1(m+1,e,i*2+1,max(m+1,l),r));
    
        
   };
   
   function<void(int,int,int,int,int)> update1=[&](int s,int e,int i,int pos,int val)->void{
        if(s==e){
            t[i]=val;return;
        }

        int m=(s+e)/2;
        if(pos<=m) update1(s,m,i*2,pos,val);
        else update1(m+1,e,i*2+1,pos,val);   
        
        t[i]=max(t[i*2],t[i*2+1]);        
        
        
   };
   
   
   
   auto get_pair=[&](int vb,int c)->int{
        
        int b=comp[vb];
        
  
        
        int l=comp[vb+1];
        int low=0,high=(int)b_entry.size()-1;
        int r=-1;
        
       
        
        while(low<=high){
            
            int mi=(low+high)/2;
            
            if(entry[*b_entry.find_by_order(mi)]<=c) high=mi-1;
            else{
                r=mi;
                low=mi+1;
            }

        }
        
        
        
        if(r==-1) return -inf;
        
    
        r=*b_entry.find_by_order(r);
       
        int res=max(res,get1(0,m-1,1,l,r));
      
        return res;   
    
   };
   

   
   auto update_pair=[&](pair<int,int> p)->void{
        
        int b=comp[p.first];
        int c=p.second;
        
        if(entry[b]==-1){
            
            int ind=b_entry.order_of_key(b);
            ind--;
            vector<int> to_remove;
            
            while(ind>=0){
                if(entry[*b_entry.find_by_order(ind)]<=c){
                    to_remove.push_back(*b_entry.find_by_order(ind));
                    ind--;
                }
                else break;
            }
            
            
            for(auto x:to_remove){
                entry[x]=-1;
                b_entry.erase(b_entry.find_by_order(b_entry.order_of_key(x)));
                update1(0,m-1,1,x,-inf);
            }
            
            // debug(v[b],to_remove);
            
            // debug(v[b],to_remove,b_entry);
            
            b_entry.insert(b);
            entry[b]=c;
            update1(0,m-1,1,b,c+v[b]);
            
            
            ind=b_entry.order_of_key(b+1);
            
            if(ind==b_entry.size()) return;
          
            int temp=*b_entry.find_by_order(ind);
            if(entry[temp]>=c){
                entry[b]=-1;
                b_entry.erase(b_entry.find_by_order(b_entry.order_of_key(b)));
                update1(0,m-1,1,b,-inf);
            }
        
            
            
        }
        else{
            if(c>entry[b]){
                entry[b]=c;
                update1(0,m-1,1,b,c+v[b]);
                int ind=b_entry.order_of_key(b);
                ind--;
                vector<int> to_remove;
                
                while(ind>=0){
                    if(entry[*b_entry.find_by_order(ind)]<=c){
                        to_remove.push_back(*b_entry.find_by_order(ind));
                        ind--;
                    }
                    else break;
                }
                
                for(auto x:to_remove){
                    entry[x]=-1;
                    b_entry.erase(b_entry.find_by_order(b_entry.order_of_key(x)));
                    update1(0,m-1,1,x,-inf);
                }
            }
        }
        
    
        
   };
   
   
   
   
   
   for(int i=0;i<n;){
        
        int j=i;
        
        vector<pair<int,int>> temp;
        
        while(j<n and (g[i][0]==g[j][0])){
            
            ans=max(ans,g[j][0]+get_pair(g[j][1],g[j][2]));
            
            // debug(j,ans);
            
            int b=g[j][1];
            int c=g[j][2];
            
            //taking this b as max
            // then i have to find max c in range 0,comp[b-1]
            //if this c is greater than my current c then i can take that pair
            
            int max_c=get(0,m-1,1,0,comp[b-1],true);
            
            if(max_c>c) temp.push_back({b,max_c});
            
            //now my b will act as min and i have to find greatest index in range comp[b+1],m-1 such that its value is less than my current c
            int low=comp[b+1],high=m-1;
            
            int ind=-1;
            
            while(low<=high){
                
                int mi=(low+high)/2;
                
                // find if min_c from range [mi,m-1] is less than my current_c
                
                int min_c=get(0,m-1,1,mi,m-1,false);
                
                if(min_c<c){
                    ind=mi;
                    low=mi+1;
                }
                else{
                    high=mi-1;
                }
                
            }
            
            if(ind!=-1) temp.push_back({v[ind],c});
            update(0,m-1,1,comp[b],c);
            j++;    
                    
        }
        
        i=j;
        
        
        for(auto x:temp) update_pair(x);
      
       
        
   }
   
   
   cout<<ans;
    

   
   
}
 
signed main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    freopen("error.txt","w",stderr);
    int Tc=1;
    // cin>>Tc;
 
    for(int tc=1;tc<=Tc;tc++)
    {
        Excuse_Me(tc);
    }
   
    return 0;
}

Compilation message

team.cpp: In function 'void Excuse_Me(long long int)':
team.cpp:43:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |    for(int i=0;i<v.size();i++) comp[v[i]]=i;
      |                ~^~~~~~~~~
team.cpp: In lambda function:
team.cpp:140:13: warning: unused variable 'b' [-Wunused-variable]
  140 |         int b=comp[vb];
      |             ^
team.cpp: In lambda function:
team.cpp:214:19: warning: comparison of integer expressions of different signedness: 'long long int' and '__gnu_pbds::detail::bin_search_tree_set<long long int, __gnu_pbds::null_type, std::less_equal<long long int>, __gnu_pbds::detail::tree_traits<long long int, __gnu_pbds::null_type, std::less_equal<long long int>, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  214 |             if(ind==b_entry.size()) return;
      |                ~~~^~~~~~~~~~~~~~~~
team.cpp: In function 'int main()':
team.cpp:330:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  330 |     freopen("error.txt","w",stderr);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
team.cpp: In function 'void Excuse_Me(long long int)':
team.cpp:169:13: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
  169 |         int res=max(res,get1(0,m-1,1,l,r));
      |             ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 392 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 392 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 544 KB Output is correct
11 Correct 97 ms 14720 KB Output is correct
12 Correct 52 ms 11464 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct
14 Incorrect 79 ms 14600 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 544 KB Output is correct
11 Correct 97 ms 14720 KB Output is correct
12 Correct 52 ms 11464 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct
14 Incorrect 79 ms 14600 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 544 KB Output is correct
11 Correct 97 ms 14720 KB Output is correct
12 Correct 52 ms 11464 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct
14 Incorrect 79 ms 14600 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 0 ms 600 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 544 KB Output is correct
11 Correct 97 ms 14720 KB Output is correct
12 Correct 52 ms 11464 KB Output is correct
13 Correct 62 ms 11468 KB Output is correct
14 Incorrect 79 ms 14600 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 392 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 344 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Incorrect 1 ms 348 KB Output isn't correct
18 Halted 0 ms 0 KB -