oj.uz

Submission #42934

# Submission time Handle Problem Language Result Execution time Memory
42934 2018-03-06T10:55:49 Z funcsr Divide and conquer (IZhO14_divide) C++14
100 / 100
 81 ms 23820 KB 
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;

typedef pair<long long, long long> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define MAX_N (1<<17)
long long seg[MAX_N*2-1];
void update(int k, long long v) {
  k += MAX_N-1;
  seg[k] = max(seg[k], v);
  while (k > 0) {
    k = (k-1)/2;
    seg[k] = max(seg[k*2+1], seg[k*2+2]);
  }
}
long long query(int a, int b, int k=0, int l=0, int r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return seg[k];
  return max(query(a, b, k*2+1, l, (l+r)/2), query(a, b, k*2+2, (l+r)/2, r));
}

int N;
long long X[100000], A[100000], B[100000];

signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cin >> N;
  rep(i, N) cin >> X[i] >> A[i] >> B[i];
  rep(i, N-1) A[i+1] += A[i];
  rep(i, N-1) B[i+1] += B[i];
  vector<long long> xs;
  rep(i, N) xs.pb(B[i]-X[i]);
  sort(all(xs)); uniq(xs);
  long long m = 0;
  for (int l=N-1; l>=0; l--) {
    update(index(xs, B[l]-X[l]), A[l]);
    long long border = (l>0?B[l-1]:0)-X[l];
    long long v = query(index(xs, border), MAX_N);
    if (v != 0) m = max(m, v - (l>0?A[l-1]:0));
  }
  cout << m << "\n";
  return 0;
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 2 ms 592 KB Output is correct
7 Correct 2 ms 592 KB Output is correct
8 Correct 2 ms 592 KB Output is correct
9 Correct 2 ms 592 KB Output is correct
10 Correct 2 ms 596 KB Output is correct
11 Correct 2 ms 636 KB Output is correct
12 Correct 2 ms 656 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 840 KB Output is correct
3 Correct 2 ms 840 KB Output is correct
4 Correct 2 ms 896 KB Output is correct
5 Correct 2 ms 896 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 2 ms 1008 KB Output is correct
8 Correct 2 ms 1028 KB Output is correct
9 Correct 2 ms 1064 KB Output is correct
10 Correct 4 ms 1092 KB Output is correct
11 Correct 5 ms 1416 KB Output is correct
12 Correct 5 ms 1516 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1640 KB Output is correct
2 Correct 9 ms 2032 KB Output is correct
3 Correct 8 ms 2232 KB Output is correct
4 Correct 43 ms 5228 KB Output is correct
5 Correct 38 ms 6668 KB Output is correct
6 Correct 81 ms 11856 KB Output is correct
7 Correct 70 ms 13716 KB Output is correct
8 Correct 73 ms 15672 KB Output is correct
9 Correct 70 ms 17480 KB Output is correct
10 Correct 76 ms 19156 KB Output is correct
11 Correct 77 ms 21328 KB Output is correct
12 Correct 73 ms 23820 KB Output is correct