oj.uz

답안 #204946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
204946 2020-02-27T14:23:21 Z Haunted_Cpp Simple (info1cup19_simple) C++17
100 / 100
 576 ms 42704 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 pushdown (int l, int r, int node) {
    if (seg[node].mx_even != -1) {
      seg[node].mx_even += seg[node].lazy;
    }
    if (seg[node].mx_odd != -1) {
      seg[node].mx_odd += seg[node].lazy;
    }  
    if (seg[node].mn_even < 1e16) {
      seg[node].mn_even += seg[node].lazy;
    }
    if (seg[node].mn_odd < 1e16) {
      seg[node].mn_odd += seg[node].lazy;
    }
    if (l != r) {
      seg[2 * node + 1].lazy += seg[node].lazy;
      seg[2 * node + 2].lazy += seg[node].lazy;
    }
    if (seg[node].lazy & 1) {
      swap (seg[node].mx_even, seg[node].mx_odd);
      swap (seg[node].mn_even, seg[node].mn_odd);
    }
    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) {     
      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 (l != r) {
        seg[2 * node + 1].lazy += delta;
        seg[2 * node + 2].lazy += delta;
      }
      if (delta & 1) {
        swap (seg[node].mx_even, seg[node].mx_odd);
        swap (seg[node].mn_even, seg[node].mn_odd);
      }
      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

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1144 KB Output is correct
2 Correct 12 ms 1144 KB Output is correct
3 Correct 13 ms 1400 KB Output is correct
4 Correct 13 ms 1400 KB Output is correct
5 Correct 13 ms 1400 KB Output is correct
6 Correct 13 ms 1400 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 194 ms 20564 KB Output is correct
2 Correct 412 ms 40984 KB Output is correct
3 Correct 417 ms 41080 KB Output is correct
4 Correct 416 ms 40996 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 1144 KB Output is correct
2 Correct 12 ms 1144 KB Output is correct
3 Correct 13 ms 1400 KB Output is correct
4 Correct 13 ms 1400 KB Output is correct
5 Correct 13 ms 1400 KB Output is correct
6 Correct 13 ms 1400 KB Output is correct
7 Correct 194 ms 20564 KB Output is correct
8 Correct 412 ms 40984 KB Output is correct
9 Correct 417 ms 41080 KB Output is correct
10 Correct 416 ms 40996 KB Output is correct
11 Correct 236 ms 21112 KB Output is correct
12 Correct 576 ms 41528 KB Output is correct
13 Correct 507 ms 42296 KB Output is correct
14 Correct 543 ms 41464 KB Output is correct
15 Correct 493 ms 42704 KB Output is correct
16 Correct 139 ms 39032 KB Output is correct