oj.uz

Submission #280104

# Submission time Handle Problem Language Result Execution time Memory
280104 2020-08-22T13:35:23 Z Haunted_Cpp I want to be the very best too! (NOI17_pokemonmaster) C++17
35 / 100
 216 ms 9804 KB 
/**
 *  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;

map<int, set<int>> where_is;
set<int> cnt;

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 + 50);
  //~ 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.insert(type[i]);
    seg.range_update(i, i, cnt.size());
    //~ debug(how);
  }
  auto get_rightmost = [&](int delta, const set<int> &cur) {
    auto where = cur.upper_bound(delta);
    if (where == cur.end()) return c;
    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);
      }
      type[coluna] = new_type;
      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;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4984 KB Output is correct
2 Correct 44 ms 5112 KB Output is correct
3 Correct 55 ms 5752 KB Output is correct
4 Correct 36 ms 4984 KB Output is correct
5 Correct 46 ms 4984 KB Output is correct
6 Correct 53 ms 5752 KB Output is correct
7 Correct 40 ms 4968 KB Output is correct
8 Correct 41 ms 4984 KB Output is correct
9 Correct 33 ms 5028 KB Output is correct
10 Correct 50 ms 5752 KB Output is correct
11 Correct 48 ms 5112 KB Output is correct
12 Correct 62 ms 7544 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4984 KB Output is correct
2 Correct 44 ms 5112 KB Output is correct
3 Correct 55 ms 5752 KB Output is correct
4 Correct 36 ms 4984 KB Output is correct
5 Correct 46 ms 4984 KB Output is correct
6 Correct 53 ms 5752 KB Output is correct
7 Correct 40 ms 4968 KB Output is correct
8 Correct 41 ms 4984 KB Output is correct
9 Correct 33 ms 5028 KB Output is correct
10 Correct 50 ms 5752 KB Output is correct
11 Correct 48 ms 5112 KB Output is correct
12 Correct 62 ms 7544 KB Output is correct
13 Correct 100 ms 6776 KB Output is correct
14 Correct 196 ms 6944 KB Output is correct
15 Correct 216 ms 7416 KB Output is correct
16 Correct 151 ms 6648 KB Output is correct
17 Correct 149 ms 6904 KB Output is correct
18 Correct 125 ms 7804 KB Output is correct
19 Correct 124 ms 6760 KB Output is correct
20 Correct 143 ms 6648 KB Output is correct
21 Correct 120 ms 6648 KB Output is correct
22 Correct 164 ms 7544 KB Output is correct
23 Correct 156 ms 6904 KB Output is correct
24 Correct 215 ms 9804 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 4984 KB Output is correct
2 Correct 44 ms 5112 KB Output is correct
3 Correct 55 ms 5752 KB Output is correct
4 Correct 36 ms 4984 KB Output is correct
5 Correct 46 ms 4984 KB Output is correct
6 Correct 53 ms 5752 KB Output is correct
7 Correct 40 ms 4968 KB Output is correct
8 Correct 41 ms 4984 KB Output is correct
9 Correct 33 ms 5028 KB Output is correct
10 Correct 50 ms 5752 KB Output is correct
11 Correct 48 ms 5112 KB Output is correct
12 Correct 62 ms 7544 KB Output is correct
13 Runtime error 2 ms 896 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -