結果
問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
ユーザー |
![]() |
提出日時 | 2017-02-28 20:13:20 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 176 ms / 5,000 ms |
コード長 | 1,982 bytes |
コンパイル時間 | 1,239 ms |
コンパイル使用メモリ | 96,752 KB |
実行使用メモリ | 22,800 KB |
最終ジャッジ日時 | 2024-09-22 10:32:17 |
合計ジャッジ時間 | 8,065 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <iostream> #include <algorithm> #include <unordered_map> #include <vector> using namespace std; struct BIT{ vector<int> bit;int size; BIT(int n){ size=n;bit=vector<int>(n+1); } //a[i]=x void add(int i,int x){ i+=1; while(i<=size)bit[i]+=x,i+=i&-i; } //a[k] (k<i)の要素の和を求める int sum(int i){ int s=0; while(i>0)s+=bit[i],i-=i&-i; return s; } }; inline int calc_score(int stars, int users) { return 50 * stars + (500 * stars) / (8 + 2 * (users + 1)); } int main() { int N, T; cin >> N; vector<int> L(N); for(int i = 0; i < N; i++) cin >> L[i]; cin >> T; vector<string> names; unordered_map<string, int> name_to_id; vector<int> id, query; for(int i = 0; i < T; i++) { string name, P; cin >> name >> P; if(!name_to_id.count(name)) { name_to_id[name] = names.size(); names.push_back(name); } id.push_back(name_to_id[name]); query.push_back(P == "?" ? -1 : P[0] - 'A'); } vector<int> score(names.size()); vector<int> scores(1); vector<int> solved(N); for(int i = 0; i < T; i++) { if(query[i] == -1) continue; score[id[i]] = (score[id[i]] / T + calc_score(L[query[i]], solved[query[i]])) * T + T - i - 1; scores.push_back(score[id[i]]); solved[query[i]]++; } std::sort(scores.begin(), scores.end()); BIT bit(scores.size()); solved = vector<int>(N); score = vector<int>(names.size()); for(int i = 0; i < T; i++) { if(query[i] == -1) { int lid = lower_bound(scores.begin(), scores.end(), score[id[i]]) - scores.begin(); cout << bit.sum(scores.size()) - bit.sum(lid + 1) + 1 << endl; continue; } bit.add(lower_bound(scores.begin(), scores.end(), score[id[i]]) - scores.begin(), -1); score[id[i]] = (score[id[i]] / T + calc_score(L[query[i]], solved[query[i]])) * T + T - i - 1; bit.add(lower_bound(scores.begin(), scores.end(), score[id[i]]) - scores.begin(), 1); solved[query[i]]++; } }