Submission #536295

#	Time	Username	Problem	Language	Result	Execution time	Memory
536295		cadmiumsky	Triple Jump (JOI19_jumps)	C++14	100 / 100	1564 ms	68012 KiB

jumps

#include <bits/stdc++.h>
using namespace std;

const int nmax = 5e5 + 5;
const int nextpow = 1 << 20;
const int inf = 1e9;

int n;
vector<int> v;

namespace AINT {
  struct Node {
    int vab, x, sum;
    Node operator +(const Node& a) const {
      return Node{-inf, max(x, a.x), max(sum, a.sum)};
    }
    void tag(const int& a)  {
      if(vab < a)
        vab = a, sum = max(sum, a + x);
    } 
  } aint[nmax * 4], iden = Node{-inf, -inf, -inf};
  int lazy[nmax * 4];
  void apply(int node, int cl, int cr) {
    if(lazy[node] == -1)
      return;
    aint[node].tag(lazy[node]);
    if(cl != cr) {
      lazy[2 * node] = max(lazy[node], lazy[2 * node]);
      lazy[2 * node + 1] = max(lazy[node], lazy[2 * node + 1]);
    }
    //aint[node] = aint[node] + aint[2 * node] + aint[2 * node + 1];
    lazy[node] = -1;
  }
  void prop(int node, int cl, int cr) {
    apply(node, cl, cr);
    if(cl == cr)
      return;
    int mid = cl + cr >> 1;
    apply(2 * node, cl, mid);
    apply(2 * node + 1, mid + 1, cr);
  }
  void upd(int l, int r, int val, int node = 1, int cl = 0, int cr = n) {
    prop(node, cl, cr);
    if(cr < l || r < cl)
      return;
    if(l <= cl && cr <= r) {
      //cout << "cine " << l << ' ' << cl << ' ' << cr << ' ' << r << "  +" << val << '\n';
      lazy[node] = val;
      prop(node, cl, cr);
      return;
    }
    int mid = cl + cr >> 1;
    upd(l, r, val, 2 * node, cl, mid);
    upd(l, r, val, 2 * node + 1, mid + 1, cr);
    int sus = aint[node].vab;
    aint[node] = aint[2 * node] + aint[2 * node + 1];
    aint[node].vab = sus;
  }
  Node query(int l, int r, int node = 1, int cl = 0, int cr = n) {
    prop(node, cl, cr);
    if(cr < l || r < cl)
      return iden;
    if(l <= cl && cr <= r) {
      //cout << "cum " << l << ' ' << cl << ' ' << cr << ' ' << r << ' ' << aint[node].x << ' ' << aint[node].vab << ' ' << aint[node].sum << '\n';
      return aint[node];
    }
    int mid = cl + cr >> 1;
    Node rez = query(l, r, 2 * node, cl, mid) + query(l, r, 2 * node + 1, mid + 1, cr);
    return rez;
  }
  int qry(int l, int r) {
    return query(l, r).sum;
  }
  void construct(int node = 1, int cl = 0, int cr = n) {
    aint[node] = iden;
    lazy[node] = -1;
    if(cl == cr) {
      aint[node].x = v[cl];
      return;
    }
    int mid = cl + cr >> 1;
    construct(2 * node, cl, mid);
    construct(2 * node + 1, mid + 1, cr);
    aint[node] = aint[2 * node] + aint[2 * node + 1];
    return;
  }

};

vector<tuple<int,int,int> > rez;
vector<int> qs[nmax];

static void candid(int l, int r) {
  int sim = r + (r - l);
  if(sim >= n)
    return;
  //cerr << l << ' ' << r << ' ' <<sim << ' ' << n << '\n';
  AINT::upd(sim, n, v[l] + v[r]);
  return;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q;
  cin >> n;
  v.resize(n);
  #define stack deobiceicineintreaba
  vector<int> stack;
  for(auto &x : v) cin >> x;
  stack.push_back(n);
  v.push_back(-1e9 -5);
  AINT::construct();
  v.back() *= -1;
  //cerr << v.size() << '\n',
  cin >> q;
  rez.resize(q);
  int i = 0;
  for(auto &[a, b, c] : rez)
    cin >> a >> b, --a, --b, c = 0, qs[a].push_back(i++);
  int l, r, val;
  for(int i = n - 1; i >= 0; i--) {
    while(v[stack.back()] <= v[i]) {
      candid(i, stack.back());
      stack.pop_back();
    }
    candid(i, stack.back());
     
    stack.push_back(i);
    for(auto x : qs[i]) {
      tie(l, r, val) = rez[x];
      val = AINT::qry(l, r);
      //cout << val << '\n';
      rez[x] = {l, r, val};
    }
  }
  for(auto [a, b, c] : rez)
    cout << c << '\n';
}
#warning cine cu scopul de a fucking intreba

Compilation message (stderr)

jumps.cpp:140:2: warning: #warning cine cu scopul de a fucking intreba [-Wcpp]
  140 | #warning cine cu scopul de a fucking intreba
      |  ^~~~~~~
jumps.cpp: In function 'void AINT::prop(int, int, int)':
jumps.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'void AINT::upd(int, int, int, int, int, int)':
jumps.cpp:52:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'AINT::Node AINT::query(int, int, int, int, int)':
jumps.cpp:67:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'void AINT::construct(int, int, int)':
jumps.cpp:81:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:119:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |   for(auto &[a, b, c] : rez)
      |             ^
jumps.cpp:137:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  137 |   for(auto [a, b, c] : rez)
      |            ^

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54