結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー | nola_suz |
提出日時 | 2016-11-19 00:18:07 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 940 ms / 5,000 ms |
コード長 | 4,479 bytes |
コンパイル時間 | 1,341 ms |
コンパイル使用メモリ | 126,404 KB |
実行使用メモリ | 46,896 KB |
最終ジャッジ日時 | 2023-10-23 15:02:32 |
合計ジャッジ時間 | 22,715 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,348 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 4 ms
4,348 KB |
testcase_04 | AC | 4 ms
4,348 KB |
testcase_05 | AC | 4 ms
4,348 KB |
testcase_06 | AC | 4 ms
4,348 KB |
testcase_07 | AC | 4 ms
4,348 KB |
testcase_08 | AC | 4 ms
4,348 KB |
testcase_09 | AC | 4 ms
4,348 KB |
testcase_10 | AC | 3 ms
4,348 KB |
testcase_11 | AC | 4 ms
4,348 KB |
testcase_12 | AC | 391 ms
11,176 KB |
testcase_13 | AC | 638 ms
21,764 KB |
testcase_14 | AC | 557 ms
21,884 KB |
testcase_15 | AC | 685 ms
21,552 KB |
testcase_16 | AC | 616 ms
21,668 KB |
testcase_17 | AC | 613 ms
21,748 KB |
testcase_18 | AC | 390 ms
11,172 KB |
testcase_19 | AC | 570 ms
21,864 KB |
testcase_20 | AC | 560 ms
21,796 KB |
testcase_21 | AC | 646 ms
21,552 KB |
testcase_22 | AC | 652 ms
21,796 KB |
testcase_23 | AC | 388 ms
11,168 KB |
testcase_24 | AC | 607 ms
21,724 KB |
testcase_25 | AC | 356 ms
11,192 KB |
testcase_26 | AC | 320 ms
11,668 KB |
testcase_27 | AC | 630 ms
21,556 KB |
testcase_28 | AC | 650 ms
21,712 KB |
testcase_29 | AC | 561 ms
21,772 KB |
testcase_30 | AC | 670 ms
21,552 KB |
testcase_31 | AC | 665 ms
21,804 KB |
testcase_32 | AC | 559 ms
21,852 KB |
testcase_33 | AC | 606 ms
21,764 KB |
testcase_34 | AC | 373 ms
11,232 KB |
testcase_35 | AC | 699 ms
21,572 KB |
testcase_36 | AC | 365 ms
11,500 KB |
testcase_37 | AC | 940 ms
46,896 KB |
testcase_38 | AC | 602 ms
30,448 KB |
testcase_39 | AC | 529 ms
30,448 KB |
testcase_40 | AC | 525 ms
30,448 KB |
testcase_41 | AC | 724 ms
29,736 KB |
testcase_42 | AC | 753 ms
29,736 KB |
testcase_43 | AC | 247 ms
13,948 KB |
testcase_44 | AC | 242 ms
14,060 KB |
testcase_45 | AC | 880 ms
46,896 KB |
ソースコード
#include <cstdlib> #include <cmath> #include <climits> #include <cfloat> #include <map> #include <set> #include <iostream> #include <string> #include <vector> #include <algorithm> #include <sstream> #include <complex> #include <stack> #include <queue> #include <cstdio> #include <cstring> #include <iterator> #include <bitset> #include <unordered_set> #include <unordered_map> #include <fstream> #include <iomanip> #include <cassert> //#include <utility> //#include <memory> //#include <functional> //#include <deque> //#include <cctype> //#include <ctime> //#include <numeric> //#include <list> //#include <iomanip> //#if __cplusplus >= 201103L //#include <array> //#include <tuple> //#include <initializer_list> //#include <forward_list> // //#define cauto const auto& //#else //#endif using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<int> vint; typedef vector<vector<int> > vvint; typedef vector<long long> vll, vLL; typedef vector<vector<long long> > vvll, vvLL; #define VV(T) vector<vector< T > > template <class T> void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){ v.assign(a, vector<T>(b, t)); } template <class F, class T> void convert(const F &f, T &t){ stringstream ss; ss << f; ss >> t; } #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define reep(i,a,b) for(int i=(a);i<(b);++i) #define rep(i,n) reep((i),0,(n)) #define ALL(v) (v).begin(),(v).end() #define PB push_back #define F first #define S second #define mkp make_pair #define RALL(v) (v).rbegin(),(v).rend() #define DEBUG #ifdef DEBUG #define dump(x) cout << #x << " = " << (x) << endl; #define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; #else #define dump(x) #define debug(x) #endif #define MOD 1000000007LL #define EPS 1e-8 #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3fLL #define maxs(x,y) x=max(x,y) #define mins(x,y) x=min(x,y) template <class Tp> class fenwick_tree{ std::vector<Tp> bit; public: fenwick_tree(){} explicit fenwick_tree(std::size_t n) : bit(n + 1) {} Tp sum(std::size_t i) const{ Tp s = 0; while(i){ s += bit[i]; i -= i & -i; } return s; } void add(std::size_t i, Tp x){ while(i < bit.size()){ bit[i] += x; i += i & -i; } } void clear(){ bit.clear(); } void assign(std::size_t n){ bit.assign(n + 1, Tp()); } void swap(fenwick_tree &f){ bit.swap(f.bit); } }; void mainmain(){ int n; cin>>n; vint v(n); rep(i,n) cin>>v[i]; int T; cin>>T; typedef pair<pii,vint> P; map<string,P> ma; vint cnt(n,1); vector<pair<string,string>> input(T); set<pii> score; vector<pii> w; rep(i,T){ string s; cin>>s; string t; cin>>t; input[i]=mkp(s,t); if(t[0]=='?'){ // set<pii>::iterator it = score.upper_bound(pii(-ma[s].F.F, -ma[s].F.S)); // int ans = distance(score.begin(), it); // ans = score.size()-ans; // cout<<ans+1<<endl; w.PB(pii(-ma[s].F.F,-ma[s].F.S)); continue; } if(ma.count(s)==0){ ma[s]=mkp(pii(0,i),vint(n)); score.insert(pii(0,i)); } int tt = t[0]-'A'; ma[s].S[tt]=(50*v[tt] + (50*v[tt]/(0.8+0.2*cnt[tt]))); score.erase(pii(-ma[s].F.F, -ma[s].F.S)); ma[s].F.F-=ma[s].S[tt]; ma[s].F.S=i; score.insert(pii(-ma[s].F.F, -ma[s].F.S)); cnt[tt]++; } sort(ALL(w)); ma=map<string,P>(); cnt=vint(n,1); score.clear(); fenwick_tree<int> bit(w.size()+100); rep(i,T){ // cout<<i<<endl; string s=input[i].F; string t=input[i].S; if(t[0]=='?'){ // set<pii>::iterator it = score.upper_bound(pii(-ma[s].F.F, -ma[s].F.S)); // int ans = distance(score.begin(), it); // ans = score.size()-ans; // cout<<ans+1<<endl; int idx = lower_bound(ALL(w), pii(-ma[s].F.F, -ma[s].F.S))-w.begin(); int ans = bit.sum(w.size()+11) - bit.sum(idx+1); cout<<ans+1<<endl; continue; } if(ma.count(s)==0){ ma[s]=mkp(pii(0,i),vint(n)); score.insert(pii(0,i)); } int tt = t[0]-'A'; ma[s].S[tt]=(50*v[tt] + (50*v[tt]/(0.8+0.2*cnt[tt]))); score.erase(pii(-ma[s].F.F, -ma[s].F.S)); int idx = lower_bound(ALL(w), pii(-ma[s].F.F, -ma[s].F.S))-w.begin(); bit.add(idx+1, -1); ma[s].F.F-=ma[s].S[tt]; ma[s].F.S=i; score.insert(pii(-ma[s].F.F, -ma[s].F.S)); idx = lower_bound(ALL(w), pii(-ma[s].F.F, -ma[s].F.S))-w.begin(); bit.add(idx+1, 1); cnt[tt]++; } } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); cout<<fixed<<setprecision(20); mainmain(); }