oj.uz

Submission #525947

# Submission time Handle Problem Language Result Execution time Memory
525947 2022-02-13T09:33:37 Z Dilshod_Imomov Divide and conquer (IZhO14_divide) C++17
17 / 100
 1 ms 352 KB 
# 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, int val ) {
   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 ), val );
   int j = get( v * 2 + 1, m + 1, r, max( tl, m + 1 ), tr, val );
   if ( x[i] - d[i - 1] >= val ) {
      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 j = get( 1, 1, n, 1, i - 1, x[i] - d[i] );
      // 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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 316 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 316 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Incorrect 1 ms 332 KB Output isn't correct
17 Halted 0 ms 0 KB -