oj.uz

Submission #204947

# Submission time Handle Problem Language Result Execution time Memory
204947 2020-02-27T14:25:20 Z Haunted_Cpp Simple (info1cup19_simple) C++17
100 / 100
 561 ms 37624 KB 
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <algorithm>
#include <cstring>
#include <cassert>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i < (int) b; i++)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define f first
#define s second
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};

void setIO(string nome) {
  ios_base::sync_with_stdio(0); cin.tie(0);
  freopen ((nome + ".in").c_str(), "r", stdin);
  freopen ((nome + ".out").c_str(), "w", stdout);
}

const int N = 2e5 + 5;
int a [N];

struct Node {
  i64 mx_odd, mn_odd;
  i64 mx_even, mn_even;
  i64 lazy;
  Node () {
    mx_odd = mx_even = -1;
    mn_even = mn_odd = 1e17;
    lazy = 0;
  }
  void merge (Node l, Node r) {
    mx_odd = max (l.mx_odd, r.mx_odd);
    mx_even = max (l.mx_even, r.mx_even);
    mn_even = min (l.mn_even, r.mn_even);
    mn_odd = min (l.mn_odd, r.mn_odd);
  }
};

struct SegmentTree {
  vector<Node> seg;
  SegmentTree (int n) {
    seg.clear();
    seg.resize(4 * n);
    build (0, n - 1, 0);
  }
  void build (int l, int r, int node) {
    if (l == r) {
      if (a[l] & 1) seg[node].mx_odd = seg[node].mn_odd = a[l];
      else seg[node].mx_even = seg[node].mn_even = a[l];
    } else {
      int mid = l + (r - l) / 2;
      build (l, mid, 2 * node + 1);
      build (mid + 1, r, 2 * node + 2);
      seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
    }
  }
  void add (int node, i64 delta) {
    if (seg[node].mx_even != -1) {
      seg[node].mx_even += delta;
    }
    if (seg[node].mx_odd != -1) {
      seg[node].mx_odd += delta;
    }  
    if (seg[node].mn_even < 1e16) {
      seg[node].mn_even += delta;
    }
    if (seg[node].mn_odd < 1e16) {
      seg[node].mn_odd += delta;
    }
    if (delta & 1) {
      swap (seg[node].mx_even, seg[node].mx_odd);
      swap (seg[node].mn_even, seg[node].mn_odd);
    }
  }
  void pushdown (int l, int r, int node) {
    add (node, seg[node].lazy);
    if (l != r) {
      seg[2 * node + 1].lazy += seg[node].lazy;
      seg[2 * node + 2].lazy += seg[node].lazy;
    }
    seg[node].lazy = 0;
  }
  void update (int ql, int qr, int delta, int l, int r, int node) {
    if (seg[node].lazy > 0) pushdown (l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {     
      add (node, delta); 
      if (l != r) {
        seg[2 * node + 1].lazy += delta;
        seg[2 * node + 2].lazy += delta;
      }
      return;
    }
    int mid = l + (r - l) / 2;
    update (ql, qr, delta, l, mid, 2 * node + 1);
    update (ql, qr, delta, mid + 1, r, 2 * node + 2);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  i64 query_odd (int ql, int qr, int l, int r, int node) {
    if (seg[node].lazy > 0) pushdown (l, r, node);
    if (l > qr || r < ql) return -1;
    if (l >= ql && r <= qr) return seg[node].mx_odd;
    int mid = l + (r - l) / 2;
    return max (query_odd (ql, qr, l, mid, 2 * node + 1), query_odd (ql, qr, mid + 1, r, 2 * node + 2));
  }
  i64 query_even (int ql, int qr, int l, int r, int node) {
    if (seg[node].lazy > 0) pushdown (l, r, node);
    if (l > qr || r < ql) return 1e18;
    if (l >= ql && r <= qr) return seg[node].mn_even;
    int mid = l + (r - l) / 2;
    return min (query_even (ql, qr, l, mid, 2 * node + 1), query_even (ql, qr, mid + 1, r, 2 * node + 2));
  }
};

int main () {
  ios_base::sync_with_stdio(0); 
  cin.tie(0);
  int n;
  cin >> n;
  F0R (i, n) cin >> a[i];
  SegmentTree seg (n);
  int q;
  cin >> q;
  while (q--) {
    int task, lo, hi;
    cin >> task >> lo >> hi;
    --lo; --hi;
    if (task == 1) {
      i64 q_even = seg.query_even (lo, hi, 0, n - 1, 0);
      if (q_even > 1e16) q_even = -1;
      i64 q_odd = seg.query_odd (lo, hi, 0, n - 1, 0);
      cout << q_even << ' ' << q_odd << '\n';
    } else {
      int delta;
      cin >> delta;
      seg.update (lo, hi, delta, 0, n - 1, 0);
    }
  } 
  return 0;
}

Compilation message

subway.cpp: In function 'void setIO(std::__cxx11::string)':
subway.cpp:38:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".in").c_str(), "r", stdin);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subway.cpp:39:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen ((nome + ".out").c_str(), "w", stdout);
   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Correct 11 ms 1144 KB Output is correct
3 Correct 14 ms 1400 KB Output is correct
4 Correct 12 ms 1400 KB Output is correct
5 Correct 13 ms 1400 KB Output is correct
6 Correct 12 ms 1400 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 19064 KB Output is correct
2 Correct 386 ms 36600 KB Output is correct
3 Correct 387 ms 36600 KB Output is correct
4 Correct 396 ms 36600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1144 KB Output is correct
2 Correct 11 ms 1144 KB Output is correct
3 Correct 14 ms 1400 KB Output is correct
4 Correct 12 ms 1400 KB Output is correct
5 Correct 13 ms 1400 KB Output is correct
6 Correct 12 ms 1400 KB Output is correct
7 Correct 181 ms 19064 KB Output is correct
8 Correct 386 ms 36600 KB Output is correct
9 Correct 387 ms 36600 KB Output is correct
10 Correct 396 ms 36600 KB Output is correct
11 Correct 222 ms 18936 KB Output is correct
12 Correct 542 ms 36028 KB Output is correct
13 Correct 508 ms 36988 KB Output is correct
14 Correct 561 ms 35832 KB Output is correct
15 Correct 458 ms 37624 KB Output is correct
16 Correct 134 ms 32632 KB Output is correct