oj.uz

답안 #394133

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
394133 2021-04-25T18:13:24 Z usachevd0 푸드 코트 (JOI21_foodcourt) C++14
13 / 100
 713 ms 35680 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) cerr << a[i];
  cerr << endl;
}
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif

const ll INF64 = 1e18;
const int maxN = 250005;
int N, M, Q;

int VL[maxN], VR[maxN], VM[maxN];
vector<int> qb[maxN];

namespace sgt1 {
  const int logN = 18;
  const int N = 1 << logN;

  struct Node {
    ll sz;
    ll min1, min2;
    ll lazy_all, lazy_min;

    Node() {
      sz = 0;
      min1 = 0;
      min2 = +INF64;
      lazy_all = lazy_min = 0;
    }
  } t[2 * N];

  void upd(int v) {
    t[v].min1 = t[v << 1].min1;
    t[v].min2 = t[v << 1].min2;
    if (t[v << 1 | 1].min1 < t[v].min1) {
      t[v].min2 = t[v].min1;
      t[v].min1 = t[v << 1 | 1].min1;
      chkmin(t[v].min2, t[v << 1 | 1].min2);
    } else if (t[v << 1 | 1].min1 < t[v].min1) {
      chkmin(t[v].min2, t[v << 1 | 1].min1);
    } else {
      chkmin(t[v].min2, t[v << 1 | 1].min2);
    }
  }

  void apply1(int v, ll d) {
    t[v].sz += d;
  }

  void apply2_all(int v, ll d) {
    t[v].min1 += d;
    t[v].min2 += d;
    t[v].lazy_all += d;
  }

  void apply2_min(int v, ll d) {
    t[v].min1 += d;
    t[v].lazy_min += d;
  }

  void push(int v) {
    for (int u : {v << 1, v << 1 | 1}) {
      if (t[v].sz) {
        apply1(u, t[v].sz);
      }
      if (t[v].lazy_all) {
        apply2_all(u, t[v].lazy_all);
      }
      if (t[v].lazy_min && t[v].min1 - t[v].lazy_min == t[u].min1) {
        apply2_min(u, t[v].lazy_min);
      }
    }
    t[v].sz = t[v].lazy_all = t[v].lazy_min = 0;
  }

  void add1(int v, int vl, int vr, int l, int r, ll d) {
    if (l > r || vr < l || r < vl) return;
    if (l <= vl && vr <= r) {
      apply1(v, d);
      apply2_all(v, d);
      return;
    } 
    int vm = (vl + vr) >> 1;
    push(v);
    add1(v << 1, vl, vm, l, r, d);
    add1(v << 1 | 1, vm + 1, vr, l, r, d);
    upd(v);
  }

  void add2(int v, int vl, int vr, int l, int r, ll d) {
    if (l > r || vr < l || r < vl) return;
    if (l <= vl && vr <= r) {
      apply2_all(v, d);
      return;
    }
    int vm = (vl + vr) >> 1;
    push(v);
    add2(v << 1, vl, vm, l, r, d);
    add2(v << 1 | 1, vm + 1, vr, l, r, d);
    upd(v);
  }

  void umax0(int v, int vl, int vr, int l, int r) {
    if (l > r || vr < l || r < vl || t[v].min1 >= 0) return;
    if (l <= vl && vr <= r && t[v].min2 > 0) {
      apply2_min(v, -t[v].min1);
      return;
    }
    int vm = (vl + vr) >> 1;
    push(v);
    umax0(v << 1, vl, vm, l, r);
    umax0(v << 1 | 1, vm + 1, vr, l, r);
    upd(v);
  }

  pll gt(int v, int vl, int vr, int i) {
    if (vl == vr) {
      return {t[v].sz, t[v].lazy_all + t[v].lazy_min};
    }
    int vm = (vl + vr) >> 1;
    push(v);
    if (i <= vm) {
      return gt(v << 1, vl, vm, i);
    } else {
      return gt(v << 1 | 1, vm + 1, vr, i);
    }
  }
}

struct Query1 {
  int l, r, c, k;
  
  Query1() {}

  void read() {
    cin >> l >> r >> c >> k;
  }
} qr1[maxN];
int qr1_t[maxN];

struct Query3 {
  int i;
  ll k;
} qr3[maxN];
int qr3_t[maxN];

namespace fnw {
  ll f[maxN];
  void reset() {
    fill(f, f + N + 1, 0);
  }
  void add(int i, ll d) {
    for (; i <= N; i += i & -i) {
      f[i] += d;
    }
  }
  void add(int l, int r, ll d) {
    add(l, d);
    add(r + 1, -d);
  }
  ll gt(int i) {
    ll ans = 0;
    for (; i >= 1; i -= i & -i) {
      ans += f[i];
    }
    return ans;
  }
}


int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M >> Q;
  int T = 0;
  int Q1 = 0;
  for (int qi = 0; qi < Q; ++qi) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      auto& q = qr1[Q1];
      q.read();
      qr1_t[Q1++] = T;

      sgt1::add1(1, 1, N, q.l, q.r, q.k);
    } else if (tp == 2) {
      int l, r, k;
      cin >> l >> r >> k;
      sgt1::add2(1, 1, N, l, r, -k);
      sgt1::umax0(1, 1, N, l, r);
    } else {
      auto& q = qr3[T];
      cin >> q.i >> q.k;
      --q.k;
      qr3_t[T++] = Q1;

      auto f = sgt1::gt(1, 1, N, q.i);
      q.k += f.fi - f.se;
    }
  }
  for (int i = 0; i < T; ++i) {
    VL[i] = -1;
    VR[i] = qr3_t[i];
  }
  while (true) {
    bool found = false;
    for (int i = 0; i < T; ++i) {
      if (VR[i] - VL[i] > 1) {
        found = true;
        VM[i] = (VL[i] + VR[i]) / 2;
        qb[VM[i]].push_back(i);
      }
    }
    if (!found) {
      break;
    }
    fnw::reset();
    for (int j = 0; j < Q1; ++j) {
      auto& q = qr1[j];
      fnw::add(q.l, q.r, q.k);
      for (int i : qb[j]) {
        if (fnw::gt(qr3[i].i) <= qr3[i].k) {
          VL[i] = VM[i];
        } else {
          VR[i] = VM[i];
        }
      }
      qb[j].clear();
    }
  }
  for (int i = 0; i < T; ++i) {
    if (VR[i] == qr3_t[i]) {
      cout << "0\n";
    } else {
      cout << qr1[VR[i]].c << '\n';
    }
  }

  return 0;
}

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 174 ms 29232 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 713 ms 35680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 156 ms 29864 KB Output is correct
2 Correct 151 ms 30040 KB Output is correct
3 Correct 149 ms 30108 KB Output is correct
4 Correct 103 ms 29252 KB Output is correct
5 Correct 139 ms 29748 KB Output is correct
6 Correct 141 ms 30104 KB Output is correct
7 Correct 72 ms 29276 KB Output is correct
8 Correct 61 ms 29196 KB Output is correct
9 Correct 100 ms 30172 KB Output is correct
10 Correct 99 ms 29320 KB Output is correct
11 Correct 138 ms 30164 KB Output is correct
12 Correct 147 ms 30148 KB Output is correct

Subtask #7
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 16 ms 26700 KB Output isn't correct
2 Halted 0 ms 0 KB -