oj.uz

Submission #536292

# Submission time Handle Problem Language Result Execution time Memory
536292 2022-03-12T18:08:38 Z cadmiumsky Triple Jump (JOI19_jumps) C++14
46 / 100
 486 ms 153676 KB 
#include <bits/stdc++.h>
#define int long long
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[nextpow], iden = Node{-inf, -inf, -inf};
  int lazy[nextpow];
  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(-2e9 -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:141:2: warning: #warning cine cu scopul de a fucking intreba [-Wcpp]
  141 | #warning cine cu scopul de a fucking intreba
      |  ^~~~~~~
jumps.cpp: In function 'void AINT::prop(long long int, long long int, long long int)':
jumps.cpp:39:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'void AINT::upd(long long int, long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'AINT::Node AINT::query(long long int, long long int, long long int, long long int, long long int)':
jumps.cpp:68:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'void AINT::construct(long long int, long long int, long long int)':
jumps.cpp:82:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
jumps.cpp: In function 'int main()':
jumps.cpp:120:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  120 |   for(auto &[a, b, c] : rez)
      |             ^
jumps.cpp:138:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  138 |   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 8 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 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 6 ms 11988 KB Output is correct
10 Correct 7 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 8 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 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 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 467 ms 36332 KB Output is correct
12 Correct 463 ms 36336 KB Output is correct
13 Correct 448 ms 36188 KB Output is correct
14 Correct 450 ms 36284 KB Output is correct
15 Correct 486 ms 36380 KB Output is correct
16 Correct 462 ms 35692 KB Output is correct
17 Correct 454 ms 35564 KB Output is correct
18 Correct 457 ms 35516 KB Output is correct
19 Correct 474 ms 36132 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 30000 KB Output is correct
2 Correct 141 ms 33676 KB Output is correct
3 Correct 150 ms 30080 KB Output is correct
4 Correct 298 ms 30004 KB Output is correct
5 Correct 278 ms 30068 KB Output is correct
6 Correct 293 ms 30000 KB Output is correct
7 Correct 286 ms 30988 KB Output is correct
8 Correct 290 ms 31172 KB Output is correct
9 Correct 281 ms 31396 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 8 ms 11988 KB Output is correct
4 Correct 6 ms 11988 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 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 6 ms 11988 KB Output is correct
10 Correct 7 ms 11988 KB Output is correct
11 Correct 467 ms 36332 KB Output is correct
12 Correct 463 ms 36336 KB Output is correct
13 Correct 448 ms 36188 KB Output is correct
14 Correct 450 ms 36284 KB Output is correct
15 Correct 486 ms 36380 KB Output is correct
16 Correct 462 ms 35692 KB Output is correct
17 Correct 454 ms 35564 KB Output is correct
18 Correct 457 ms 35516 KB Output is correct
19 Correct 474 ms 36132 KB Output is correct
20 Correct 299 ms 30000 KB Output is correct
21 Correct 141 ms 33676 KB Output is correct
22 Correct 150 ms 30080 KB Output is correct
23 Correct 298 ms 30004 KB Output is correct
24 Correct 278 ms 30068 KB Output is correct
25 Correct 293 ms 30000 KB Output is correct
26 Correct 286 ms 30988 KB Output is correct
27 Correct 290 ms 31172 KB Output is correct
28 Correct 281 ms 31396 KB Output is correct
29 Runtime error 313 ms 153676 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -