oj.uz

Submission #90539

# Submission time Handle Problem Language Result Execution time Memory
90539 2018-12-22T09:43:35 Z inom Divide and conquer (IZhO14_divide) C++14
100 / 100
 54 ms 6544 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];
		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;
		if (t[v << 1] <= pred[pos] - x[pos]) {
			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++) {
		update(1, 1, n, i);
		ans = max(ans, preg[i] - preg[get(1, 1, n, i) - 1]);
	}
	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:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld", &n);
  ~~~~~^~~~~~~~~~~~
divide.cpp:70: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 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 440 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 2 ms 500 KB Output is correct
7 Correct 2 ms 500 KB Output is correct
8 Correct 2 ms 500 KB Output is correct
9 Correct 2 ms 500 KB Output is correct
10 Correct 2 ms 500 KB Output is correct
11 Correct 2 ms 576 KB Output is correct
12 Correct 2 ms 592 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 608 KB Output is correct
3 Correct 2 ms 608 KB Output is correct
4 Correct 2 ms 608 KB Output is correct
5 Correct 2 ms 608 KB Output is correct
6 Correct 3 ms 736 KB Output is correct
7 Correct 2 ms 736 KB Output is correct
8 Correct 2 ms 736 KB Output is correct
9 Correct 2 ms 736 KB Output is correct
10 Correct 3 ms 748 KB Output is correct
11 Correct 4 ms 876 KB Output is correct
12 Correct 4 ms 880 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 892 KB Output is correct
2 Correct 5 ms 1276 KB Output is correct
3 Correct 6 ms 1276 KB Output is correct
4 Correct 23 ms 3580 KB Output is correct
5 Correct 25 ms 3580 KB Output is correct
6 Correct 54 ms 6524 KB Output is correct
7 Correct 41 ms 6544 KB Output is correct
8 Correct 41 ms 6544 KB Output is correct
9 Correct 39 ms 6544 KB Output is correct
10 Correct 42 ms 6544 KB Output is correct
11 Correct 48 ms 6544 KB Output is correct
12 Correct 49 ms 6544 KB Output is correct