제출 #33591

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
33591		RockyB	금 캐기 (IZhO14_divide)	C++14	100 / 100	86 ms	23296 KiB

divide

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,sse3,sse4,popcnt,abm,mmx")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)5e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;
const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n;
ll ans;
int x[N], g[N];
ll d[N], s[N];

vector <ll> cmp;

int t[N << 2];
void upd(int p, int x, int v = 1, int tl = 0, int tr = n) {
	if (tl == tr) {
		t[v] = min(t[v], x);
		return;
	}
	int tm = tl + tr >> 1;
	if (p <= tm) upd(p, x, v << 1, tl, tm);
	else upd(p, x, v << 1 | 1, tm + 1, tr);
	t[v] = min(t[v << 1], t[v << 1 | 1]);
}
int get(int l, int r, int v = 1, int tl = 0, int tr = n) {
	if (l <= tl && tr <= r) return t[v];
	if (tl > r || tr < l) return inf;
	int tm = tl + tr >> 1;
	return min(get(l, r, v << 1, tl, tm), get(l, r, v << 1 | 1, tm + 1, tr));
}
int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x[i] >> s[i] >> d[i];
		d[i] += d[i - 1];
		s[i] += s[i - 1];
		cmp.pb(x[i] - d[i - 1]);
	}
	sort(all(cmp));
	cmp.erase(unique(all(cmp)), cmp.end());
	memset(t, 0x3f, sizeof(t));
	for (int i = 1; i <= n; i++) {
		ll now = x[i] - d[i - 1];
		upd(lower_bound(all(cmp), now) - cmp.begin(), i);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		int p = get(lower_bound(all(cmp), x[i] - d[i]) - cmp.begin(), n);
		if (p <= n) ans = max(ans, s[i] - s[p - 1]);
	}
	cout << ans;
	ioi
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp: In function 'void upd(int, int, int, int, int)':
divide.cpp:47:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int tm = tl + tr >> 1;
              ^
divide.cpp: In function 'int get(int, int, int, int, int)':
divide.cpp:55:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int tm = tl + tr >> 1;
              ^

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