제출 #526384

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526384		Dilshod_Imomov	금 캐기 (IZhO14_divide)	C++17	100 / 100	371 ms	7016 KiB

divide

# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
# define int long long
# define fi first
# define se second
 
using namespace std;
 
const int N = 1e5 + 7;
const int mod = 1e9 + 7;
// const int INF = 1e18;
 
int x[N], g[N], d[N], t[4 * N];

void build( int v, int l, int r ) {
   if ( l == r ) {
      t[v] = l;
      return;
   }
   int m = (l + r) / 2;
   build( v * 2, l, m );
   build( v * 2 + 1, m + 1, r );
   int i = t[v * 2], j = t[v * 2 + 1];
   if ( x[ i ] - d[ i - 1 ] >= x[j] - d[j - 1] ) {
      t[v] = i;
   }
   else {
      t[v] = j;
   }
}

int get( int v, int l, int r, int tl, int tr ) {
   if ( tl > tr ) {
      return -1;
   }
   if ( l == tl && tr == r ) {
      return t[v];
   }
   int m = (l + r) / 2;
   int i = get( v * 2, l, m, tl, min( tr, m ) );
   int j = get( v * 2 + 1, m + 1, r, max( tl, m + 1 ), tr );
   if ( i != -1 && x[i] - d[i - 1] >= x[j] - d[j - 1] ) {
      return i;
   }
   return j;
}
 
int32_t main() {
   speed;
   int n;
   cin >> n;
   for ( int i = 1; i <= n; i++ ) {
      cin >> x[i] >> g[i] >> d[i];
      d[i] += d[i - 1];
      g[i] += g[i - 1];
   }
   build( 1, 1, n );
   // cout << "done" << endl;
   int mx = 0;
   for ( int i = 1; i <= n; i++ ) {
      int l = 1, r = i - 1, j = -1;
      while ( l < r ) {
         // cout << l << ' ' << r << endl;
         int m = (l + r) / 2;
         j = get( 1, 1, n, l, m );
         if ( x[j] - d[j - 1] >= x[i] - d[i] ) {
            r = m;
         }
         else {
            l = m + 1;
         }
      }
      j = l;
      // cout << i << " " << j << endl;
      if ( j != -1 && x[i] - x[j] <= d[i] - d[j - 1] ) {
         mx = max( mx, g[i] - g[j - 1] );
      }
      mx = max( mx, g[i] - g[i - 1] );
   }
   cout << mx;
}
/*
4
0 5 1
1 7 2
4 4 1
7 15 1
*/

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