oj.uz

Submission #536291

# Submission time Handle Problem Language Result Execution time Memory
536291 2022-03-12T18:07:24 Z cadmiumsky Triple Jump (JOI19_jumps) C++14
19 / 100
 4000 ms 41260 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() {
  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:139:2: warning: #warning cine cu scopul de a fucking intreba [-Wcpp]
  139 | #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:118:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  118 |   for(auto &[a, b, c] : rez)
      |             ^
jumps.cpp:136:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  136 |   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 8 ms 12056 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 9 ms 11956 KB Output is correct
9 Correct 8 ms 11992 KB Output is correct
10 Correct 9 ms 11984 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 8 ms 12056 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 9 ms 11956 KB Output is correct
9 Correct 8 ms 11992 KB Output is correct
10 Correct 9 ms 11984 KB Output is correct
11 Correct 703 ms 41260 KB Output is correct
12 Correct 665 ms 41156 KB Output is correct
13 Correct 649 ms 41208 KB Output is correct
14 Correct 740 ms 41160 KB Output is correct
15 Correct 743 ms 41200 KB Output is correct
16 Correct 730 ms 40568 KB Output is correct
17 Correct 726 ms 40524 KB Output is correct
18 Correct 686 ms 40548 KB Output is correct
19 Correct 766 ms 40976 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4083 ms 40136 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11988 KB Output is correct
2 Correct 8 ms 12056 KB Output is correct
3 Correct 7 ms 12060 KB Output is correct
4 Correct 8 ms 12116 KB Output is correct
5 Correct 8 ms 11988 KB Output is correct
6 Correct 8 ms 11988 KB Output is correct
7 Correct 8 ms 12116 KB Output is correct
8 Correct 9 ms 11956 KB Output is correct
9 Correct 8 ms 11992 KB Output is correct
10 Correct 9 ms 11984 KB Output is correct
11 Correct 703 ms 41260 KB Output is correct
12 Correct 665 ms 41156 KB Output is correct
13 Correct 649 ms 41208 KB Output is correct
14 Correct 740 ms 41160 KB Output is correct
15 Correct 743 ms 41200 KB Output is correct
16 Correct 730 ms 40568 KB Output is correct
17 Correct 726 ms 40524 KB Output is correct
18 Correct 686 ms 40548 KB Output is correct
19 Correct 766 ms 40976 KB Output is correct
20 Execution timed out 4083 ms 40136 KB Time limit exceeded
21 Halted 0 ms 0 KB -