Submission #1018041

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018041		ind1v	Divide and conquer (IZhO14_divide)	C++11	100 / 100	38 ms	9476 KiB

divide

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

int n;
int x[N], g[N], d[N];
long long pd[N], pg[N];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n;
  vector<pair<long long, int>> v1, v2;
  for (int i = 1; i <= n; i++) {
    cin >> x[i] >> g[i] >> d[i];
    pd[i] = d[i] + pd[i - 1];
    pg[i] = g[i] + pg[i - 1];
    v1.emplace_back(x[i] - pd[i], i);
    v2.emplace_back(x[i] - pd[i - 1], i);
  }
  sort(v1.begin(), v1.end(), greater<pair<long long, int>>());
  sort(v2.begin(), v2.end(), greater<pair<long long, int>>());
  int mn = 1e9;
  long long ans = -1e9;
  for (int i = 0, j = 0; i < v1.size(); i++) {
    while (j < v2.size() && v2[j].first >= v1[i].first) {
      mn = min(mn, v2[j++].second);
    }
    if (mn != 1e9) {
      ans = max(ans, pg[v1[i].second] - pg[mn - 1]);
    }
  }
  cout << ans << '\n';
  return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:27:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for (int i = 0, j = 0; i < v1.size(); i++) {
      |                          ~~^~~~~~~~~~~
divide.cpp:28:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     while (j < v2.size() && v2[j].first >= v1[i].first) {
      |            ~~^~~~~~~~~~~

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