結果
問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
ユーザー |
![]() |
提出日時 | 2019-12-13 18:06:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 580 ms / 5,000 ms |
コード長 | 1,779 bytes |
コンパイル時間 | 1,348 ms |
コンパイル使用メモリ | 131,892 KB |
実行使用メモリ | 40,276 KB |
最終ジャッジ日時 | 2024-09-22 10:36:40 |
合計ジャッジ時間 | 14,761 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #include <complex> #include <unordered_map> #include <unordered_set> #include <random> #include <cassert> #include <fstream> #include <utility> #include <functional> #include <time.h> #include <stack> #include <array> #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair<int, int> P; template<typename T> struct BIT{ //1-indexed vector<T> bit; int size; BIT(int n):size(n), bit(n+1, 0){} T sum(int i){ T s=0; while(i>0){ s+=bit[i]; i-=(i&(-i)); } return s; } void add(int i, T x){ while(i<=size){ bit[i]+=x; i+=(i&(-i)); } } }; int main() { int n; cin>>n; int l[30]; for(int i=0; i<n; i++) cin>>l[i]; int T; cin>>T; string name[100010]; char p[100010]; int cnt[30]={}; map<P, int> mp; map<string, int> s, t; mp[{0, 0}]=0; int v[100010]; for(int i=1; i<=T; i++){ cin>>name[i]>>p[i]; if(p[i]!='?'){ cnt[p[i]-'A']++; v[i]=(int)(50*l[p[i]-'A']+50*l[p[i]-'A']/(0.8+0.2*cnt[p[i]-'A'])); s[name[i]]+=v[i]; mp[{-s[name[i]], i}]=0; } } int m=0; for(auto &p:mp){ m++; p.second=m; } BIT<int> bit(m); bit.add(m, (int)s.size()); s.clear(); fill(cnt, cnt+n, 0); for(int i=1; i<=T; i++){ if(p[i]!='?'){ cnt[p[i]-'A']++; int x=mp[{-s[name[i]], t[name[i]]}]; bit.add(x, -1); s[name[i]]+=v[i]; int y=mp[{-s[name[i]], i}]; bit.add(y, 1); t[name[i]]=i; }else{ int x=mp[{-s[name[i]], t[name[i]]}]; printf("%d\n", bit.sum(x)); } } return 0; }