/**
* 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);
//~ 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);
}
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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
512 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
