oj.uz

Submission #950539

# Submission time Handle Problem Language Result Execution time Memory
950539 2024-03-20T11:52:32 Z xynex Triple Jump (JOI19_jumps) C++17
100 / 100
 959 ms 512844 KB 
/**
  * Author: Tenjin
  * Created: 27.04.2022 18:58
  * Why am I so stupid? :c
  * Slishkom slab
**/

#include <bits/stdc++.h>

 #pragma GCC optimize("inline")
 #pragma GCC optimize("-fgcse,-fgcse-lm")
 #pragma GCC optimize("-ftree-pre,-ftree-vrp")
 #pragma GCC optimize("-ffast-math")
 #pragma GCC optimize("-fipa-sra")
 #pragma GCC optimize("-fpeephole2")
 #pragma GCC optimize("-fsched-spec")
 #pragma GCC optimize("Ofast,no-stack-protector")
 #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
 #pragma GCC optimize("unroll-loops")

using namespace std;
#define ll long long
#define dl double long
#define ull unsigned long long
#define pr pair
#define vt vector
#define ff first
#define ss second
#define mp make_pair
#define sz(a) (int)a.size()
#define pb push_back
#define pf push_front
#define popB pop_back
#define popF pop_front
#define bit_count __builtin_popcount
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed << setprecision(x)

template<typename T> T get_rand(T l, T r) {
  random_device rd;
  mt19937 gen(rd());
  return uniform_int_distribution<T>(l, r)(gen);
}
template<typename T> T lcm(T a, T b) { return a * (b / __gcd(a, b)); }

template<class A>  void read(vt<A>& v);
template<class A, size_t S> void read(array<A, S>& a);
template<class T> void read(T& x) { cin >> x; }
void read(double& d) { string t; read(t); d = stod(t); }
void read(long double& d) { string t; read(t); d = stold(t); }
template<class H, class... T> void read(H& h, T&... t) { read(h); read(t...); }
template<class A> void read(vt<A>& x) { for (auto& a : x) read(a); }
template<class A, size_t S> void read(array<A, S>& x) { for (auto& a : x) read(a); }

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(vt<bool> v) { string res; for (int i = 0; i < sz(v); ++i) res += char('0' + v[i]); return res; }
template<size_t S> string to_string(bitset<S> b) { string res; for (int i = 0; i < S; ++i) res += char('0' + b[i]); return res; }
template<class T> string to_string(T v) { bool f = 1; string res; for (auto x : v) { if (!f) res += ' '; f = 0; res += to_string(x); } return res; }

template<class A> void write(A x) { cout << to_string(x); }
template<class H, class... T> void write(const H& h, const T&... t) { write(h); write(t...); }

void print() { write("\n"); }
template<class H, class... T> void print(const H& h, const T&... t) { write(h); if (sizeof...(t)) write(' '); print(t...); }

void freop(string s) {
  freopen((s + ".in").c_str(), "r", stdin);
  freopen((s + ".out").c_str(), "w", stdout);
}

const int MOD = 998244353;
const ll INF = 1e14;
const dl pi = acos(-1);
const dl eps = 1e-12;
const int sq = 700;

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, -1, 0, 1};
/* ll vs int*/

const int N = 3e6 + 5;
const int M = 2e6 + 6;

ll a[N];
int n;
ll z[N];
struct seg {
  class Node {
    public:
    ll mx, last, sum;
    Node() { last = -INF, sum = -INF, mx = -INF; }
    Node(int num) { last = -INF, sum = -INF, mx = num; }
  } t[N << 2];
  void build(int tl = 1, int tr = n, int v = 1) {
    if(tl == tr) t[v] = *new Node(a[tl]);
    else {
      int mid = (tl + tr) >> 1;
      build(tl, mid, v * 2);
      build(mid + 1, tr, v * 2 + 1);
      t[v] = *new Node(max(t[v * 2].mx, t[v * 2 + 1].mx));
    }
  }
  void push(int tl, int tr, int v) {
    if(!z[v]) return;
    if(tl != tr) {
      z[v * 2] = max(z[v * 2], z[v]);
      z[v * 2 + 1] = max(z[v * 2 + 1], z[v]);
    }
//    print("P", tl, tr, z[v], t[v].last, t[v].sum, t[v].mx);
    t[v].last = max(t[v].last, z[v]);
    t[v].sum = max(t[v].sum, t[v].last + t[v].mx);
//    print("N", t[v].sum);
    z[v] = 0;
  }
  void upd(int l, int r, ll val, int tl = 1, int tr = n, int v = 1) {
    push(tl, tr, v);
  //  print("T", l, r, val, tl, tr);
    if(tl > r || tr < l) return;
    if(tl >= l && tr <= r) {
      z[v] = max(z[v], val);
      push(tl, tr, v);
      return;
    }
    int mid = (tl + tr) >> 1;
    upd(l, r, val, tl, mid, v * 2), upd(l, r, val, mid + 1, tr, v * 2 + 1);
    t[v].mx = max(t[v * 2].mx, t[v * 2 + 1].mx);
    t[v].sum = max(t[v * 2].sum, t[v * 2 + 1].sum);
  }
  ll get(int l, int r, int tl = 1, int tr = n, int v = 1) {
    push(tl, tr, v);
    if(tl > r || tr < l) return 0;
    if(tl >= l && tr <= r) return t[v].sum;
    int mid = (tl + tr) >> 1;
    return max(get(l, r, tl, mid, v * 2), get(l, r, mid + 1, tr, v * 2 + 1));
  }
} tree;
vt<int> chg[N];
ll ans[N];
vt<pr<int, int>> qu[N];
void solve() {
   read(n);
   for(int i = 1; i <= n; ++i) {
      read(a[i]);
   }
   tree.build();
   vt<int> st;
   for(int i = 1; i <= n; ++i) {
      while(!st.empty() && a[st.back()] <= a[i]) {
        chg[st.back()].pb(i);
        st.pop_back();
      }
      if(!st.empty()) {
        chg[st.back()].pb(i);
      }
      st.push_back(i);
   }
   int q; read(q);
   for(int i = 1; i <= q; ++i) {
      int l, r; read(l, r);
      qu[l].pb({r, i});
   }
   for(int i = n; i >= 1; --i) {
      while(!chg[i].empty()) {
        int j = chg[i].back();
        chg[i].pop_back();
        int x = j - i + j;
//        print("CH", x, n, i, j, a[i] + a[j]);
        if(x <= n) {
          tree.upd(x, n, a[i] + a[j]);
        }
      }
      for(auto cur : qu[i]) {
//        print("Q", i, cur.ff);
        ans[cur.ss] = tree.get(i, cur.ff);
      }
   }
   for(int i = 1; i <= q; ++i) print(ans[i]);
}

int main() {
  //srand(time(NULL));
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  //freop("");
  int t = 1;
  //read(t);
  for (int i = 1; i <= t; ++i) {
    //write("Case #" + to_string(i) + ": ");
    solve();
  }
  return 0;
}

Compilation message

jumps.cpp: In function 'void freop(std::string)':
jumps.cpp:71:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:72:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   freopen((s + ".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 429360 KB Output is correct
2 Correct 82 ms 429396 KB Output is correct
3 Correct 82 ms 429412 KB Output is correct
4 Correct 81 ms 429396 KB Output is correct
5 Correct 81 ms 429440 KB Output is correct
6 Correct 80 ms 429392 KB Output is correct
7 Correct 82 ms 429392 KB Output is correct
8 Correct 91 ms 429392 KB Output is correct
9 Correct 81 ms 429412 KB Output is correct
10 Correct 86 ms 429472 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 429360 KB Output is correct
2 Correct 82 ms 429396 KB Output is correct
3 Correct 82 ms 429412 KB Output is correct
4 Correct 81 ms 429396 KB Output is correct
5 Correct 81 ms 429440 KB Output is correct
6 Correct 80 ms 429392 KB Output is correct
7 Correct 82 ms 429392 KB Output is correct
8 Correct 91 ms 429392 KB Output is correct
9 Correct 81 ms 429412 KB Output is correct
10 Correct 86 ms 429472 KB Output is correct
11 Correct 265 ms 445936 KB Output is correct
12 Correct 273 ms 445780 KB Output is correct
13 Correct 269 ms 445864 KB Output is correct
14 Correct 270 ms 445840 KB Output is correct
15 Correct 274 ms 445776 KB Output is correct
16 Correct 266 ms 445328 KB Output is correct
17 Correct 295 ms 445332 KB Output is correct
18 Correct 273 ms 445036 KB Output is correct
19 Correct 266 ms 445784 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 453124 KB Output is correct
2 Correct 146 ms 453000 KB Output is correct
3 Correct 149 ms 453756 KB Output is correct
4 Correct 196 ms 453212 KB Output is correct
5 Correct 196 ms 453268 KB Output is correct
6 Correct 193 ms 453204 KB Output is correct
7 Correct 192 ms 453200 KB Output is correct
8 Correct 204 ms 453140 KB Output is correct
9 Correct 224 ms 453208 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 429360 KB Output is correct
2 Correct 82 ms 429396 KB Output is correct
3 Correct 82 ms 429412 KB Output is correct
4 Correct 81 ms 429396 KB Output is correct
5 Correct 81 ms 429440 KB Output is correct
6 Correct 80 ms 429392 KB Output is correct
7 Correct 82 ms 429392 KB Output is correct
8 Correct 91 ms 429392 KB Output is correct
9 Correct 81 ms 429412 KB Output is correct
10 Correct 86 ms 429472 KB Output is correct
11 Correct 265 ms 445936 KB Output is correct
12 Correct 273 ms 445780 KB Output is correct
13 Correct 269 ms 445864 KB Output is correct
14 Correct 270 ms 445840 KB Output is correct
15 Correct 274 ms 445776 KB Output is correct
16 Correct 266 ms 445328 KB Output is correct
17 Correct 295 ms 445332 KB Output is correct
18 Correct 273 ms 445036 KB Output is correct
19 Correct 266 ms 445784 KB Output is correct
20 Correct 196 ms 453124 KB Output is correct
21 Correct 146 ms 453000 KB Output is correct
22 Correct 149 ms 453756 KB Output is correct
23 Correct 196 ms 453212 KB Output is correct
24 Correct 196 ms 453268 KB Output is correct
25 Correct 193 ms 453204 KB Output is correct
26 Correct 192 ms 453200 KB Output is correct
27 Correct 204 ms 453140 KB Output is correct
28 Correct 224 ms 453208 KB Output is correct
29 Correct 871 ms 506876 KB Output is correct
30 Correct 833 ms 506452 KB Output is correct
31 Correct 797 ms 508272 KB Output is correct
32 Correct 935 ms 506848 KB Output is correct
33 Correct 954 ms 506904 KB Output is correct
34 Correct 932 ms 506200 KB Output is correct
35 Correct 868 ms 506540 KB Output is correct
36 Correct 959 ms 506160 KB Output is correct
37 Correct 921 ms 506904 KB Output is correct
38 Correct 632 ms 512844 KB Output is correct
39 Correct 618 ms 512536 KB Output is correct
40 Correct 633 ms 510948 KB Output is correct
41 Correct 603 ms 510564 KB Output is correct
42 Correct 635 ms 510768 KB Output is correct
43 Correct 619 ms 511628 KB Output is correct
44 Correct 694 ms 511900 KB Output is correct
45 Correct 699 ms 512056 KB Output is correct
46 Correct 654 ms 510512 KB Output is correct
47 Correct 646 ms 510300 KB Output is correct
48 Correct 708 ms 510292 KB Output is correct
49 Correct 668 ms 511568 KB Output is correct
50 Correct 729 ms 509960 KB Output is correct
51 Correct 730 ms 510128 KB Output is correct
52 Correct 720 ms 509308 KB Output is correct
53 Correct 758 ms 509268 KB Output is correct
54 Correct 749 ms 509080 KB Output is correct
55 Correct 766 ms 510028 KB Output is correct