Submission #715905

#	Time	Username	Problem	Language	Result	Execution time	Memory
715905		ktkerem	Divide and conquer (IZhO14_divide)	C++17	100 / 100	58 ms	9880 KiB

divide

/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 1e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n , m;std::vector<std::pair<ll , llll>> ar;
ll mx[sus * 4] , gld[sus];
void sv(ll l , ll r , ll a){
  if(l == r){
    mx[a] = ar[l].sec.fi;
    return;
  }
  ll md = (l + r)/2;
  sv(l , md , a*2);
  sv(md+1 , r , a*2+1);
  mx[a] = std::max(mx[a*2] , mx[a*2+1]);
  ll cst = 0 , g = 0;
  for(ll i = md+1;r>=i;i++){
    cst += (ar[i].fi - ar[i-1].fi) - ar[i].sec.sec;
    g+= ar[i].sec.fi;
  }
  gld[md+1] = 0;
  ll sc = 0;
  std::vector<llll> rg;
  for(ll i = md;l <= i;i--){
    gld[i] = gld[i+1] + ar[i].sec.fi;
    sc += (i == md?0:ar[i+1].fi - ar[i].fi) - ar[i].sec.sec;
    rg.pb({sc , gld[i]});
  }
  std::sort(all(rg));
  ll ind = 0;
  for(ll i = r;md+1<=i;i--){
    while(rg.size() > ind && rg[ind].fi + cst <= 0){
      mx[a] = std::max(mx[a] , g + rg[ind].sec);
      ind++;
    }
    cst += ar[i].sec.sec;
    cst -= (ar[i].fi - ar[i-1].fi);
    g-=ar[i].sec.fi;
  }
}
void solve(){
  std::cin >> n;
  ar.resize(n);
  for(ll i = 0 ; n>i;i++){
    std::cin >> ar[i].fi >> ar[i].sec.fi >> ar[i].sec.sec;
  }
  sv(0 , n-1 , 1);
  std::cout << mx[1] << "\n";
  return;/**/
}
int main(){
  std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
  ll t = 1;
  //std::cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

divide.cpp:5:78: warning: "/*" within comment [-Wcomment]
    5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
      |                                                                               
divide.cpp: In function 'void sv(ll, ll, ll)':
divide.cpp:50:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   50 |     while(rg.size() > ind && rg[ind].fi + cst <= 0){
      |           ~~~~~~~~~~^~~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52