結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
|
提出日時 | 2016-11-19 21:52:10 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 645 ms / 5,000 ms |
コード長 | 2,596 bytes |
コンパイル時間 | 1,806 ms |
コンパイル使用メモリ | 128,860 KB |
実行使用メモリ | 39,680 KB |
最終ジャッジ日時 | 2024-09-22 10:26:39 |
合計ジャッジ時間 | 17,559 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#define _USE_MATH_DEFINES#include <cstdio>#include <iostream>#include <sstream>#include <fstream>#include <iomanip>#include <algorithm>#include <cmath>#include <complex>#include <string>#include <vector>#include <list>#include <queue>#include <stack>#include <set>#include <map>#include <bitset>#include <numeric>#include <limits>#include <climits>#include <cfloat>#include <functional>#include <iterator>using namespace std;class BinaryIndexedTree{private:int n;vector<int> data;public:BinaryIndexedTree(int n){ // コンストラクタthis->n = n;data.assign(n+1, 0);}void add(int k, int x){ // k番目の要素にxを加算する++ k;while(k <= n){data[k] += x;k += k & -k;}}int sum(int k){ // 区間[0,k]の総和を返す++ k;int ret = 0;while(k > 0){ret += data[k];k -= k & -k;}return ret;}int sum(int a, int b){ // 区間[a,b]の総和を返すreturn sum(b) - sum(a-1);}};int getScore(int n, int k){return 50 * n + (500 * n) / (8 + 2 * k);}int main(){int n;cin >> n;vector<int> level(n);for(int i=0; i<n; ++i)cin >> level[i];int t;cin >> t;vector<string> name(t);vector<char> p(t);for(int i=0; i<t; ++i)cin >> name[i] >> p[i];vector<int> submitNum(n, 0);map<string, int> sum;map<pair<int, int>, int> index;for(int i=0; i<t; ++i){if(p[i] != '?'){int x = p[i] - 'A';++ submitNum[x];sum[name[i]] += getScore(level[x], submitNum[x]);index[make_pair(sum[name[i]], -i)];}}int cnt = 0;for(auto& p : index){p.second = cnt;++ cnt;}BinaryIndexedTree bit(index.size());map<string, int> lastSubmit;submitNum.assign(n, 0);sum.clear();for(int i=0; i<t; ++i){if(p[i] != '?'){if(sum.find(name[i]) != sum.end())bit.add(index[make_pair(sum[name[i]], lastSubmit[name[i]])], -1);int x = p[i] - 'A';++ submitNum[x];sum[name[i]] += getScore(level[x], submitNum[x]);lastSubmit[name[i]] = -i;bit.add(index[make_pair(sum[name[i]], lastSubmit[name[i]])], +1);}else{int ans = bit.sum(index[make_pair(sum[name[i]], lastSubmit[name[i]])], index.size()-1);cout << ans << endl;}}return 0;}