Submission #31761

#	Time	Username	Problem	Language	Result	Execution time	Memory
31761		ruhanhabib39	Divide and conquer (IZhO14_divide)	C++14	100 / 100	73 ms	7876 KiB

divide

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

const int MAXN = 1e5;

int N;
int X[MAXN + 10], G[MAXN + 10], D[MAXN + 10];
long long gs[MAXN + 10], ds[MAXN + 10];

long long mxt[4 * MAXN + 10];

void init(int cn, int b, int e) {
   if(b == e) {
      mxt[cn] = X[b] - ds[b-1];
      // cerr << "mxt[" << b << "] = " << mxt[cn] << "\n";
      return;
   }
   int m = (b + e) / 2;
   init(2*cn, b, m); init(2*cn+1, m+1, e);
   mxt[cn] = max(mxt[2*cn], mxt[2*cn+1]);
}

int get(int cn, int b, int e, int l, int r, long long mv) {
   if(r < b || l > e) return INF;
   if(mxt[cn] < mv) return INF;
   if(b == e) return b;
   int m = (b + e) / 2;
   int L = get(2*cn, b, m, l, r, mv);
   if(L < INF) return L;
   return get(2*cn+1, m+1, e, l, r, mv);
}

int main() {
   scanf("%d", &N);
   for(int i = 1; i <= N; i++) {
      scanf("%d%d%d", &X[i], &G[i], &D[i]);
   }
   for(int i = 1; i <= N; i++) {
      gs[i] = G[i] + gs[i-1];
      ds[i] = D[i] + ds[i-1];
   }
   init(1, 1, N);
   long long res = 0;
   for(int r = 1; r <= N; r++) {
      int l = get(1, 1, N, 1, r, X[r] - ds[r]);
      // cerr << "l = " << l << "\n";
      // cerr << "my[" << r << "] = " << X[r] << " " << ds[r] << "\n";
      long long gold = gs[r] - gs[l-1];
      res = max(res, gold);
   }
   printf("%lld\n", res);
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:36:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &N);
                   ^
divide.cpp:38:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &X[i], &G[i], &D[i]);
                                           ^

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