oj.uz

Submission #90576

# Submission time Handle Problem Language Result Execution time Memory
90576 2018-12-22T14:17:41 Z inom Divide and conquer (IZhO14_divide) C++14
100 / 100
 51 ms 7288 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define fi first
#define se second
#define new new228
#define pb push_back
#define rank rank228
#define int long long
#define sz(c) (int)(c).size()
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
 
using namespace std;
using namespace __gnu_pbds;
 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("fast-math")
#pragma warning(disable : 4996)
 
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // st.oreder_of_key();

const int N = 100100;
const int MAXN = 4 * N;
const int INF = 1e15 + 7;
const int MOD = 998244353;
 
int TN = 1;

int n, ans;
int t[MAXN];
int x[N], g[N], d[N];
int preg[N], pred[N];

void update(int v, int tl, int tr, int pos) {
	if (tl == tr) {
		t[v] = pred[pos - 1] - (x[pos] - x[1]);
		return;
	} else {
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			update(v << 1, tl, tm, pos);
		} else {
			update(v << 1 | 1, tm + 1, tr, pos);
		}
		t[v] = min(t[v << 1], t[v << 1 | 1]);
	}
}

int get(int v, int tl, int tr, int pos) {
	if (tl == tr) {
		return tl;
	} else {
		int tm = (tl + tr) >> 1;
		// printf("t[%lld] = %lld\n", v << 1, t[v << 1]);
		if (t[v << 1] <= pred[pos] - (x[pos] - x[1])) {
			return get(v << 1, tl, tm, pos);
		} else {
			return get(v << 1 | 1, tm + 1, tr, pos);
		}
	}
}

void solve() {
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld %lld", x + i, g + i, d + i);
		preg[i] = preg[i - 1] + g[i]; pred[i] = pred[i - 1] + d[i];
	}
	/*for (int i = 1; i <= n; i++) {
		printf("preg[%lld] = %lld, pred[%lld] = %lld\n", i, preg[i], i, pred[i]);
	}
	printf("\n");*/
	for (int i = 1; i <= n; i++) {
		update(1, 1, n, i);
		ans = max(ans, preg[i] - preg[get(1, 1, n, i) - 1]);
		// printf("%lld %lld %lld\n", get(1, 1, n, i) - 1, preg[i] - preg[get(1, 1, n, i) - 1], ans);
	}
	printf("%lld\n", ans);
	return;
}

signed main() {
    // in; out;  // cin >> TN;
    while (TN--) { solve(); }
    return 0;
}

Compilation message

divide.cpp:23:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable : 4996)
 
divide.cpp: In function 'void solve()':
divide.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
divide.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld %lld", x + i, g + i, d + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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 384 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 2 ms 644 KB Output is correct
7 Correct 2 ms 644 KB Output is correct
8 Correct 2 ms 644 KB Output is correct
9 Correct 2 ms 644 KB Output is correct
10 Correct 2 ms 644 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 760 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 840 KB Output is correct
7 Correct 2 ms 840 KB Output is correct
8 Correct 2 ms 840 KB Output is correct
9 Correct 2 ms 916 KB Output is correct
10 Correct 3 ms 944 KB Output is correct
11 Correct 4 ms 1236 KB Output is correct
12 Correct 4 ms 1348 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1464 KB Output is correct
2 Correct 5 ms 1912 KB Output is correct
3 Correct 5 ms 1912 KB Output is correct
4 Correct 22 ms 4204 KB Output is correct
5 Correct 25 ms 4204 KB Output is correct
6 Correct 51 ms 7160 KB Output is correct
7 Correct 40 ms 7184 KB Output is correct
8 Correct 39 ms 7184 KB Output is correct
9 Correct 38 ms 7184 KB Output is correct
10 Correct 41 ms 7288 KB Output is correct
11 Correct 48 ms 7288 KB Output is correct
12 Correct 48 ms 7288 KB Output is correct