oj.uz

Submission #536293

# Submission time Handle Problem Language Result Execution time Memory
536293 2022-03-12T18:09:52 Z cadmiumsky Triple Jump (JOI19_jumps) C++14
46 / 100
 494 ms 91564 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12080 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12084 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12080 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12084 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 475 ms 26744 KB Output is correct
12 Correct 467 ms 26668 KB Output is correct
13 Correct 478 ms 26628 KB Output is correct
14 Correct 466 ms 26700 KB Output is correct
15 Correct 463 ms 26700 KB Output is correct
16 Correct 472 ms 26116 KB Output is correct
17 Correct 494 ms 26060 KB Output is correct
18 Correct 465 ms 25976 KB Output is correct
19 Correct 461 ms 26612 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 21060 KB Output is correct
2 Correct 138 ms 22884 KB Output is correct
3 Correct 136 ms 21052 KB Output is correct
4 Correct 280 ms 21160 KB Output is correct
5 Correct 275 ms 21072 KB Output is correct
6 Correct 274 ms 21068 KB Output is correct
7 Correct 273 ms 21060 KB Output is correct
8 Correct 270 ms 21052 KB Output is correct
9 Correct 284 ms 21152 KB Output is correct

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 6 ms 11988 KB Output is correct
3 Correct 6 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 6 ms 12080 KB Output is correct
6 Correct 6 ms 11988 KB Output is correct
7 Correct 6 ms 11988 KB Output is correct
8 Correct 7 ms 11988 KB Output is correct
9 Correct 7 ms 12084 KB Output is correct
10 Correct 6 ms 11988 KB Output is correct
11 Correct 475 ms 26744 KB Output is correct
12 Correct 467 ms 26668 KB Output is correct
13 Correct 478 ms 26628 KB Output is correct
14 Correct 466 ms 26700 KB Output is correct
15 Correct 463 ms 26700 KB Output is correct
16 Correct 472 ms 26116 KB Output is correct
17 Correct 494 ms 26060 KB Output is correct
18 Correct 465 ms 25976 KB Output is correct
19 Correct 461 ms 26612 KB Output is correct
20 Correct 285 ms 21060 KB Output is correct
21 Correct 138 ms 22884 KB Output is correct
22 Correct 136 ms 21052 KB Output is correct
23 Correct 280 ms 21160 KB Output is correct
24 Correct 275 ms 21072 KB Output is correct
25 Correct 274 ms 21068 KB Output is correct
26 Correct 273 ms 21060 KB Output is correct
27 Correct 270 ms 21052 KB Output is correct
28 Correct 284 ms 21152 KB Output is correct
29 Runtime error 248 ms 91564 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -