제출 #590274

#제출 시각아이디문제언어결과실행 시간메모리
590274Do_you_copy3단 점프 (JOI19_jumps)C++14
100 / 100
884 ms75944 KiB
#include <bits/stdc++.h> #define taskname "test" #define fi first #define se second #define pb push_back #define faster ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; using ll = long long; using pii = pair <ll, ll>; using pil = pair <ll, ll>; using pli = pair <ll, ll>; using pll = pair <ll, ll>; using ull = unsigned ll; mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count()); ll min(const ll &a, const ll &b){ return (a < b) ? a : b; } ll max(const ll &a, const ll &b){ return (a > b) ? a : b; } //const ll Mod = 1000000009; //const ll Mod2 = 999999999989; //only use when required const ll maxN = 5e5 + 1; ll n; ll a[maxN]; vector <ll> Q; vector <pii> p; ll ans[maxN]; pii st[maxN * 4]; ll lazy[maxN * 4]; struct TQuery{ ll l, r, idx; }; TQuery q[maxN]; void build(ll id = 1, ll l = 1, ll r = n){ if (l == r){ st[id].fi = st[id].se = a[l]; return; } ll mid = (l + r) / 2; build(id * 2, l, mid); build(id * 2 + 1, mid + 1, r); st[id].fi = st[id].se = max(st[id * 2].se, st[id * 2 + 1].se); } void pull(ll id){ if (lazy[id]){ st[id * 2].fi = max(st[id * 2].fi, st[id * 2].se + lazy[id]); st[id * 2 + 1].fi = max(st[id * 2 + 1].fi, st[id * 2 + 1].se + lazy[id]); lazy[id * 2] = max(lazy[id * 2], lazy[id]); lazy[id * 2 + 1] = max(lazy[id * 2 + 1], lazy[id]); lazy[id] = 0; } } void update(ll id, ll i, ll j, ll val, ll l = 1, ll r = n){ if (r < i || l > j) return; if (i <= l && r <= j){ st[id].fi = max(st[id].fi, st[id].se + val); lazy[id] = max(lazy[id], val); return; } pull(id); ll mid = (l + r) / 2; update(id * 2, i, j, val, l, mid); update(id * 2 + 1, i, j, val, mid + 1, r); st[id].fi = max(st[id * 2].fi, st[id * 2 + 1].fi); } ll get(ll id, ll i, ll j, ll l = 1, ll r = n){ if (r < i || l > j) return 0; if (i <= l && r <= j){ return st[id].fi; } pull(id); ll mid = (l + r) / 2; return max(get(id * 2, i, j, l, mid), get(id * 2 + 1, i, j, mid + 1, r)); } void create(){ for (ll i = n; i >= 1; --i){ while (!Q.empty() && a[i] >= a[Q.back()]){ p.pb({i, Q.back()}); Q.pop_back(); } if (!Q.empty()) p.pb({i, Q.back()}); Q.pb(i); } sort(p.begin(), p.end(), greater<pair<ll, ll>>()); } void Init(){ cin >> n; for (ll i = 1; i <= n; ++i) cin >> a[i]; create(); build(); ll qq; cin >> qq; for (ll i = 1; i <= qq; ++i){ cin >> q[i].l >> q[i].r; q[i].idx = i; } sort(q + 1, q + qq + 1,[](const auto &i, const auto &j){ return i.l > j.l; }); ll j = 0; for (ll i = 1; i <= qq; ++i){ while (j < p.size() && p[j].fi >= q[i].l){ update(1, 2 * p[j].se - p[j].fi, n, a[p[j].se] + a[p[j].fi]); ++j; } ans[q[i].idx] = get(1, q[i].l, q[i].r); } for (ll i = 1; i <= qq; ++i) cout << ans[i] << "\n"; } int main(){ if (fopen(taskname".inp", "r")){ freopen(taskname".inp", "r", stdin); //freopen(taskname".out", "w", stdout); } faster; ll tt = 1; //cin >> tt; while (tt--){ Init(); } }

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

jumps.cpp: In function 'void Init()':
jumps.cpp:114:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |         while (j < p.size() && p[j].fi >= q[i].l){
      |                ~~^~~~~~~~~~
jumps.cpp: In function 'int main()':
jumps.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...