結果

問題 No.449 ゆきこーだーの雨と雪 (4)
ユーザー PachicobuePachicobue
提出日時 2018-02-23 19:06:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 315 ms / 5,000 ms
コード長 7,669 bytes
コンパイル時間 3,305 ms
コンパイル使用メモリ 222,508 KB
最終ジャッジ日時 2025-01-05 08:27:37
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
#define show(x) cerr << #x << " = " << x << endl
using namespace std;
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
os << "(" << p.first << "," << p.second
<< ")";
return os;
}
struct OrderedSet {
public:
static constexpr int POOL_SIZE = 100000;
private:
struct Node {
using T = pair<int, int>;
using Ptr = Node*;
using PtrPair = pair<Ptr, Ptr>;
Node() : left{}, right{}, value{}, size{1} {}
Node(const T& value) : left{}, right{}, value{value}, size{1} {}
Ptr left, right;
T value;
int size;
static void serialize(Ptr a, vector<T>& v)
{
if (a == nullptr) {
return;
} else {
serialize(a->left, v);
v.push_back(a->value);
serialize(a->right, v);
}
}
static unsigned xor128()
{
static unsigned x = 123456789;
static unsigned y = 362436069;
static unsigned z = 521288629;
static unsigned w = 88675123;
const unsigned t = x ^ (x << 11);
x = y;
y = z;
z = w;
return w = (w ^ (w << 19)) ^ (t ^ (t >> 8));
}
static unsigned getRand(const int maximum)
{
return xor128() % maximum;
}
static int getSize(const Ptr a)
{
return (a == nullptr) ? 0 : a->size;
}
static Ptr update(Ptr a)
{
a->size = getSize(a->left) + getSize(a->right) + 1;
return a;
}
static Ptr merge(Ptr a, Ptr b)
{
if (a == nullptr) {
return b;
} else if (b == nullptr) {
return a;
}
const unsigned asize = getSize(a);
const unsigned bsize = getSize(b);
if (getRand(asize + bsize) < asize) {
a->right = merge(a->right, b);
return update(a);
} else {
b->left = merge(a, b->left);
return update(b);
}
}
static PtrPair split(Ptr a, const int k) // size = (k,n-k)
{
if (a == nullptr) {
return make_pair(Ptr{}, Ptr{});
}
if (k <= getSize(a->left)) {
const PtrPair s = split(a->left, k);
a->left = s.second;
return make_pair(s.first, update(a));
} else {
const PtrPair s = split(a->right, k - getSize(a->left) - 1);
a->right = s.first;
return make_pair(update(a), s.second);
}
}
static Ptr insert(Ptr a, const int k, Ptr b)
{
const PtrPair s = split(a, k);
return merge(merge(s.first, b), s.second);
}
static PtrPair erase(Ptr a, const int k)
{
const PtrPair sr = split(a, k + 1);
const PtrPair sl = split(sr.first, k);
return make_pair(merge(sl.first, sr.second), sl.second);
}
};
using Ptr = typename Node::Ptr;
using PtrPair = typename Node::PtrPair;
Ptr root;
int head = 0;
static Node pool[POOL_SIZE];
Ptr alloc(const Node::T& x)
{
assert(head < POOL_SIZE);
pool[head].value = x;
pool[head].size = 1;
pool[head].left = nullptr;
pool[head].right = nullptr;
head++;
return pool + head - 1;
}
void garbage_collect()
{
vector<T> v;
Node::serialize(root, v);
head = 0;
root = nullptr;
for (int i = 0; i < v.size(); i++) {
root = Node::insert(root, i, alloc(v[i]));
}
}
public:
using T = typename Node::T;
OrderedSet() : root{} {}
int size() const
{
return Node::getSize(root);
}
void insert(const T& value)
{
if (head == POOL_SIZE) {
garbage_collect();
}
const int pos = lowerBound(value);
root = Node::insert(root, pos, alloc(value));
}
int lowerBound(const T& x) const
{
int res = 0;
Ptr v = root;
while (v) {
if (x < v->value) {
v = v->left;
} else if (x == v->value) {
return res + Node::getSize(v->left);
} else {
res += Node::getSize(v->left) + 1;
v = v->right;
}
}
return res;
}
int upperBound(const T& x) const
{
int res = 0;
Ptr v = root;
while (v) {
if (x <= v->value) {
v = v->left;
} else if (x == v->value) {
return res + Node::getSize(v->left);
} else {
res += Node::getSize(v->left) + 1;
v = v->right;
}
}
return res;
}
void eraseAt(const int k)
{
assert(0 <= k);
assert(k < Node::getSize(root));
Ptr p;
tie(root, p) = Node::erase(root, k);
if (p != nullptr) {
p->left = Ptr{};
p->right = Ptr{};
}
}
void erase(const T& value)
{
const int pos = lowerBound(value);
eraseAt(pos);
}
bool eraseWithCheck(const T& value)
{
const int pos = lowerBound(value);
if (pos == size()) {
return false;
} else if (upperBound(value) == pos) {
return false;
} else {
eraseAt(pos);
return true;
}
}
T get(int k) const
{
assert(0 <= k);
assert(k < Node::getSize(root));
Ptr v = root;
while (v != nullptr) {
const int s = Node::getSize(v->left);
if (s > k) {
v = v->left;
} else if (s == k) {
return v->value;
} else {
v = v->right;
k -= s + 1;
}
}
return v->value;
}
void set(const int k, const T& value)
{
assert(0 <= k);
assert(k < Node::getSize(root));
const PtrPair sr = Node::split(root, k + 1);
const PtrPair sl = Node::split(sr.first, k);
const Ptr lr = sl.second;
lr->value = value;
root = Node::merge(Node::merge(sl.first, lr), sr.second);
}
};
OrderedSet::Node OrderedSet::pool[OrderedSet::POOL_SIZE];
ostream& operator<<(ostream& os, const OrderedSet& st)
{
os << "[";
for (int i = 0; i < st.size(); i++) {
os << st.get(i) << ",";
}
os << "]" << endl;
return os;
}
int main()
{
cin.tie(0);
ios::sync_with_stdio(false);
int N;
cin >> N;
using S = pair<int, int>;
vector<int> level(N);
for (int i = 0; i < N; i++) {
cin >> level[i];
}
int T;
cin >> T;
map<string, S> score;
vector<int> solved(N, 0);
OrderedSet st;
for (int t = 0; t < T; t++) {
string name;
cin >> name;
char P;
cin >> P;
if (P == '?') {
const S s = score[name];
cout << 1 + st.lowerBound(s) << "\n";
} else {
const int p = P - 'A';
if (score.find(name) == score.end()) {
} else {
st.erase(score[name]);
}
solved[p]++;
score[name] = {score[name].first - 50 * level[p] - 250 * level[p] / (4 + solved[p]), t};
st.insert(score[name]);
}
}
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0