Submission #1051998

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051998	2024-08-10T10:59:25 Z	vjudge1	Divide and conquer (IZhO14_divide)	C++17	Compilation error	0 ms	0 KB

divide

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
// skibidi rizz
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
#define endl "\n"
#define int ll
#define F first     
#define S second
#define db double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
using namespace std;
const   ll inf = 1e18,MOD=998244353,N=2e5+10,MN=1e9+7,lim=1e6;
const long db Pie=acos(-1);
//...and justice for all
int binpow(int a,int p); 
struct mine{
  int x,g,d;
};
mine a[N];
int n;
int ans=-inf;
void rec(int l,int r){
  if(l==r){
    ans=max(ans,a[l].g);
    return ;
  }
  int m=(l+r)/2;
  rec(l,m);
  rec(m+1,r); 
  int curg=0,cure=0;
  vector<pair<int,int>>v;
  int last=0;
  for(int i=m+1;i<=r;i++){
    v.pb({a[i].d-(a[i].x-a[m+1].x),a[i].g+last});
    last+=a[i].g;
  }
  sort(v.begin(),v.end());
  // for(int i=0;i<v.size();i++){
  //   cout<<v[i].F<<' ';
  // }
  // cout<<endl;
  vector<int>suf(v.size()+1,-inf);
  for(int i=v.size()-1;i>=0;i--){
    suf[i]=max(suf[i+1],v[i].S);
  }
  for(int i=m;i>=l;i--){
    cure+=a[i].d;
    
    cure-=(a[i+1].x-a[i].x);
    // cout<<cure<<" ";
    curg+=a[i].g;
    int lx=0,rx=v.size()-1;
    int res=-1;
    while(lx<=rx){
      int mid=(lx+rx)/2;
      if(-cure<=v[mid].F){
        rx=mid-1;
        res=mid;
      }
      else{
        lx=mid+1;
      }
    }
    // cout<<endl<<res;
    if(res!=-1){
      if(res==v.size()){
        ans=max(curg);
      }
      else ans=max(ans,suf[res]+curg);
    }
  }
}
const void solve(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i].x>>a[i].g>>a[i].d;
  }
  rec(0,n-1);
  cout<<ans<<endl;
}
main() {
    srand(time(NULL));
    IOS;
    // freopen("divide.in", "r", stdin);
    // freopen("divide.out", "w", stdout);
    int UwU=1;
    // cin>>UwU;      
    for(int i=1;i<=UwU;i++) { 
      // cout<<"Case "<<i<<": ";
        solve(); 
      // cout<<endl;
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}
// int binmul(int a,int b){}
int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

Compilation message

divide.cpp: In function 'void rec(long long int, long long int)':
divide.cpp:88:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |       if(res==v.size()){
      |          ~~~^~~~~~~~~~
divide.cpp:89:21: error: no matching function for call to 'max(long long int&)'
   89 |         ans=max(curg);
      |                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from divide.cpp:20:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
divide.cpp:89:21: note:   candidate expects 2 arguments, 1 provided
   89 |         ans=max(curg);
      |                     ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from divide.cpp:20:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
divide.cpp:89:21: note:   candidate expects 3 arguments, 1 provided
   89 |         ans=max(curg);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from divide.cpp:20:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
divide.cpp:89:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   89 |         ans=max(curg);
      |                     ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from divide.cpp:20:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
divide.cpp:89:21: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   89 |         ans=max(curg);
      |                     ^
divide.cpp: At global scope:
divide.cpp:103:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  103 | main() {
      | ^~~~