Submission #280072

#	Time	Username	Problem	Language	Result	Execution time	Memory
280072		Haunted_Cpp	Hotspot (NOI17_hotspot)	C++17	0 / 100	6 ms	5248 KiB

hotspot

/**
 *  author: Haunted_Cpp
**/
 
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int MAX_N = 5e4 + 5;

set<int> where_is[MAX_N];
vector<bool> cnt(MAX_N, false);

class SegmentTree {
private:
  struct Node {
    int sum, lazy;
    Node() {
      sum = 0;
      lazy = 0;
    }
  };
  vector<Node> seg;
  const int LO, HI;
  void push(int l, int r, int node) {
    if (seg[node].lazy == 0) return;
    seg[node].sum += (r - l + 1) * 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 range_update(int ql, int qr, int delta, int l, int r, int node) {
    push(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      seg[node].lazy = delta;
      push(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_update(ql, qr, delta, l, mid, 2 * node + 1);
    range_update(ql, qr, delta, mid + 1, r, 2 * node + 2);
    seg[node].sum = seg[2 * node + 1].sum + seg[2 * node + 2].sum;
  }
  int sum(int l, int r, int node, int where) {
    push(l, r, node);
    if (l > where || r < where) return 0;
    if (l == r) return seg[node].sum;
    const int mid = l + (r - l) / 2;
    return sum(l, mid, 2 * node + 1, where) + sum(mid + 1, r, 2 * node + 2, where);
  }
public:
  SegmentTree(int n) : LO(0), HI(n - 1) {
    seg.clear();
    seg.resize(4 * n);
  }
  void range_update(int ql, int qr, int delta) {
    range_update(ql, qr, delta, LO, HI, 0);
  }
  int sum(int where) {
    return sum(LO, HI, 0, where);
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); 
  int r, c, q;
  cin >> r >> c >> q;
  assert(r == 1);
  vector<int> type(c);
  for (int i = 0; i < c; i++) {
    int foo;
    cin >> foo;
    assert(foo == i + 1);
  }
  SegmentTree seg(c);
  int how = 0;
  
  for (int i = 0; i < c; i++) {
    cin >> type[i];
    where_is[type[i]].insert(c);
    where_is[type[i]].insert(i);
    how += (cnt[type[i]] == false);
    cnt[type[i]] = true;
    seg.range_update(i, i, how);
    debug(how);
  }
  auto get_rightmost = [&](int delta, const set<int> &cur) {
    return *cur.upper_bound(delta);
  };
  auto get_leftmost = [&](int delta, const set<int> &cur) {
    auto where = cur.lower_bound(delta);
    if (where == cur.begin()) return -1;
    return *(prev(where));
  };
  
  while(q--) {
    int task;
    cin >> task;
    if (task == 1) {
      int linha, coluna, new_type;
      cin >> coluna >> linha >> new_type;
      --coluna;
      --linha;
      assert(linha == 0);
      int old_type = type[coluna];
      if (get_leftmost(coluna, where_is[old_type]) == -1) {
        int dir = get_rightmost(coluna, where_is[old_type]);
        seg.range_update(coluna, dir - 1, -1);
      }
      where_is[old_type].erase(coluna);
      if (get_leftmost(coluna, where_is[new_type]) == -1) {
        int dir = get_rightmost(coluna, where_is[new_type]);
        seg.range_update(coluna, dir - 1, +1);
      }
      where_is[new_type].insert(coluna);
    } else {
      int linha, coluna, max_lvl;
      cin >> coluna >> linha >> max_lvl;
      --coluna;
      --linha;
      assert(linha == 0);
      if (max_lvl < coluna + 1) {
        cout << 0 << '\n';
        continue;
      }
      cout << seg.sum(min(c - 1, max(max_lvl - 1, coluna))) << '\n';
    }
  }
  return 0;
}

Compilation message (stderr)

hotspot.cpp: In function 'int main()':
hotspot.cpp:22:20: warning: statement has no effect [-Wunused-value]
   22 | #define debug(...) 47
      |                    ^~
hotspot.cpp:105:5: note: in expansion of macro 'debug'
  105 |     debug(how);
      |     ^~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 18
• Subtask 5: 0 / 26
• Subtask 6: 0 / 36