結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
|
提出日時 | 2016-11-19 11:30:18 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 593 ms / 5,000 ms |
コード長 | 2,556 bytes |
コンパイル時間 | 2,515 ms |
コンパイル使用メモリ | 191,992 KB |
実行使用メモリ | 34,176 KB |
最終ジャッジ日時 | 2024-09-22 10:25:03 |
合計ジャッジ時間 | 15,208 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include "bits/stdc++.h"using namespace std;#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))#define rep(i,j) FOR(i,0,j)#define each(x,y) for(auto &(x):(y))#define mp make_pair#define mt make_tuple#define all(x) (x).begin(),(x).end()#define debug(x) cout<<#x<<": "<<(x)<<endl#define smax(x,y) (x)=max((x),(y))#define smin(x,y) (x)=min((x),(y))#define MEM(x,y) memset((x),(y),sizeof (x))#define sz(x) (int)(x).size()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;typedef vector<ll> vll;template<class Val>struct BinaryIndexedTree{int n;vector<Val> t;BinaryIndexedTree(){}BinaryIndexedTree(int _n):n(_n+1), t(_n+1){}void add(int k, Val val){k++;while(k < n){t[k] += val;k += (k&-k);}}Val sum(int k){Val r = 0;while(k > 0){r += t[k];k -= (k&-k);}return r;}Val sum(int l, int r){return sum(r) - sum(l);}};typedef BinaryIndexedTree<int> BIT;int f(int x, int y) {return 50 * x + 500 * x / (8 + 2 * y);}int main(){ios::sync_with_stdio(false);cin.tie(0);int N;while(cin >> N) {vi L(N);vi cnt(N);rep(i, N) cin >> L[i];int T;cin >> T;vector<string> Name(T);vector<char> P(T);map<string, int> pt;vector<pii> pos;pos.emplace_back(0, 0);rep(i, T) {cin >> Name[i] >> P[i];if(P[i] != '?') {P[i] -= 'A';pt[Name[i]] += f(L[P[i]], ++cnt[P[i]]);pos.emplace_back(pt[Name[i]], -i);}}sort(all(pos));BIT sum(sz(pos));sum.add(0, sz(pt));map<string, int> last;pt.clear();fill_n(cnt.begin(), N, 0);auto g = [&](int p, int las) {auto it = lower_bound(all(pos), mp(p, -las));assert(it != pos.end());return it - pos.begin();};rep(i, T) {if(P[i] != '?') {int k = g(pt[Name[i]], last[Name[i]]);sum.add(k, -1);pt[Name[i]] += f(L[P[i]], ++cnt[P[i]]);last[Name[i]] = i;k = g(pt[Name[i]], i);sum.add(k, 1);} else {int k = g(pt[Name[i]], last[Name[i]]);int ans = sum.sum(k, sz(pos));cout << ans << endl;}}}}