Submission #36392

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
36392	2017-12-08 15:10:49	cheater2k	Divide and conquer (IZhO14_divide)	C++14	100 / 100	69 ms	11536 KiB

divide

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
const long long inf = 1e18;
int n;
long long x[N], g[N], d[N];
long long T[N];
long long ans;
vector<long long> z; // for compression
void upd(int x, long long val) { for(; x < N; x += x & -x) T[x] = min(T[x], val); }
long long get(int x) { long long res = inf; for (; x > 0; x -= x & -x) res = min(res, T[x]); return res; }
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> x[i] >> g[i] >> d[i]; // (coordinate, gold, energy)
    d[i] += d[i-1];
    g[i] += g[i-1];
  }
  for (int i = 1; i <= n; ++i) {
    // compress all values
    z.push_back(d[i] - x[i]);
    z.push_back(d[i-1] - x[i]);
  }
  sort(z.begin(), z.end());
  z.resize(distance(z.begin(), unique(z.begin(), z.end())));
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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