oj.uz

Submission #1052034

# Submission time Handle Problem Language Result Execution time Memory
1052034 2024-08-10T11:10:48 Z daulet Divide and conquer (IZhO14_divide) C++14
0 / 100
 0 ms 348 KB 
/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
// 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=1e5+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);
  }
  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(ans,curg);
      }
      else ans=max(ans,suf[res]+curg);
    }
  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;
    lx=0,rx=v.size()-1;
    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(ans,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;
}
signed 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:82: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]
   82 |       if(res==v.size()){
      |          ~~~^~~~~~~~~~
divide.cpp:107: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]
  107 |       if(res==v.size()){
      |          ~~~^~~~~~~~~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -