█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 6843

Problema 0x7b - Mínimo número de salones para acomodar todas las clases

  • Autor: Juan Jr
  • Fecha: 2023-01-12 05:54:10 UTC (Hace 18 días)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.005 s 2 KBi
#2
Correcto
0.004 s 2 KBi
#3
Correcto
0.005 s 1 KBi
#4
Correcto
0.005 s 1 KBi
#5
Correcto
0.006 s 2 KBi
#6
Correcto
0.004 s 39 KBi
#7
Correcto
0.005 s 6 KBi
#8
Correcto
0.005 s 6 KBi
#9
Correcto
0.005 s 29 KBi
#10
Correcto
0.004 s 5 KBi
#11
Correcto
0.004 s 1 KBi
#12
Correcto
0.006 s 1 KBi
#13
Correcto
0.126 s 1 KBi
#14
Correcto
0.098 s 2 KBi
#15
Correcto
0.186 s 3 KBi
Puntos totales: 100 / 100

Código

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
#define pb push_back
#define ff first
#define ss second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define forn(i, n) for (int i = 0; i < n; ++i)
#define rforn(i, n) for (int i = n; i >= 0; --i)
#define form(i, n, m, x) for (int i = n; i < m; i += x)
#define rform(i, n, m, x) for (int i = n; i >= m; i -= x)

#ifdef LOCAL
  #include "/debug/debug.h"
#else
  #define dbg(x...)
  #define endl '\n'
#endif

template<typename T>
struct STree {
  int n; vector<T> st, lazy;
  T neutro = T(-1e9);

  STree(vector<T> &a) {
    n = sz(a);
    st.resize(n * 4);
    lazy.resize(n * 4);
    build(1, 0, n - 1, a);
  }

  T oper(T a, T b) { return max(a,b); }

  void build(int v, int tl, int tr, vector<T> &a) {
    if(tl == tr) {
      st[v] = a[tl];
      return;
    }
    int tm = tl + (tr - tl) / 2;
    build(v * 2, tl, tm, a);
    build(v * 2 + 1, tm + 1, tr, a);
    st[v] = oper(st[v * 2], st[v * 2 + 1]);
  }

  void push(int v) {
    st[v * 2] += lazy[v]; lazy[v * 2] += lazy[v];
    st[v * 2 + 1] += lazy[v]; lazy[v * 2 + 1] += lazy[v];
    lazy[v] = 0;
  }

  void upd(int v, int tl, int tr, int l, int r, T val) {
    if(tl > r || tr < l) return;
    if (l <= tl && tr <= r) {
      st[v] += val;
      lazy[v] += val;
      return;
    }
    push(v);
    int tm = tl + (tr - tl) / 2;
    upd(v * 2, tl, tm, l, r, val);
    upd(v * 2 + 1, tm + 1, tr, l, r, val);
    st[v] = oper(st[v * 2], st[v * 2 + 1]);
  }

  T query(int v, int tl, int tr, int l, int r) {
    if(tl > r || tr < l) return neutro;
    if (l <= tl && tr <= r) return st[v];
    push(v);
    int tm = tl + (tr - tl) / 2;
    return oper(query(v * 2, tl, tm, l, r), query(v * 2 + 1, tm + 1, tr, l, r));
  }

  void upd(int l, int r, T val) { upd(1, 0, n - 1, l, r, val); }
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  const int MAX = 1500;
  vector<int> v(MAX);
  STree<int> st(v);
  auto read = []() -> int {
    string s; cin >> s;
    return stoi(s.substr(0, 2)) * 60 + stoi(s.substr(3));
  };
  int n; cin >> n;
  forn (i, n) {
    int l = read();
    int r = read();
    st.upd(l, r - 1, 1);
  }
  cout << st.query(0, MAX - 1) << endl;
  return 0;
}

/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */