結果
問題 |
No.449 ゆきこーだーの雨と雪 (4)
|
ユーザー |
|
提出日時 | 2017-01-04 17:21:45 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 343 ms / 5,000 ms |
コード長 | 2,534 bytes |
コンパイル時間 | 2,301 ms |
コンパイル使用メモリ | 196,904 KB |
実行使用メモリ | 32,552 KB |
最終ジャッジ日時 | 2024-09-22 10:32:46 |
合計ジャッジ時間 | 12,757 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< ll > vl; typedef vector< vl > vvl; typedef pair< int, int > pii; typedef vector< pii > vp; typedef vector< double > vd; typedef vector< vd > vvd; typedef vector< string > vs; template< class T1, class T2 > int upmin( T1 &x, T2 v ){ if( x > v ){ x = v; return 1; } return 0; } template< class T1, class T2 > int upmax( T1 &x, T2 v ){ if( x < v ){ x = v; return 1; } return 0; } const int INF = 0x3f3f3f3f; int N; vi L; int T; vs name, P; void init(){ cin >> N; L = vi( N ); for( int i = 0; i < N; ++i ){ cin >> L[ i ]; } cin >> T; name = P = vs( T ); for( int i = 0; i < T; ++i ){ cin >> name[ i ] >> P[ i ]; } } vp vis_scr_clk; map< pii, int > mp; struct fenwick{ vi dat; fenwick( int sz ){ dat = vi( sz ); } void update( int x, int v ){ for( int i = x; i < dat.size(); i += i & -i ){ dat[ i ] += v; } } int sum( int x ){ int res = 0; for( int i = x; i > 0; i -= i & -i ){ res += dat[ i ]; } return res; } } *ftree; void preprocess(){ vi prob_ac_cnt( N ); map< string, pii > user2scr_clk; vis_scr_clk.emplace_back( 0, 0 ); for( int i = 0; i < T; ++i ){ if( P[ i ][ 0 ] == '?' ) continue; int p = P[ i ][ 0 ] - 'A'; pii v = user2scr_clk[ name[ i ] ]; v.first += 50 * L[ p ] + 500 * L[ p ] / ( 8 + 2 * ++prob_ac_cnt[ p ] ); v.second = -i; user2scr_clk[ name[ i ] ] = v; vis_scr_clk.emplace_back( v ); } sort( vis_scr_clk.begin(), vis_scr_clk.end() ); vis_scr_clk.erase( unique( vis_scr_clk.begin(), vis_scr_clk.end() ), vis_scr_clk.end() ); for( int i = 0; i < vis_scr_clk.size(); ++i ){ mp[ vis_scr_clk[ i ] ] = i + 1; } ftree = new fenwick( vis_scr_clk.size() + 1 ); } void solve(){ vi prob_ac_cnt( N ); map< string, pii > user2scr_clk; for( int i = 0; i < T; ++i ){ if( P[ i ][ 0 ] == '?' ){ pii v = user2scr_clk[ name[ i ] ]; cout << ftree->sum( vis_scr_clk.size() ) - ftree->sum( mp[ v ] ) + 1 << endl; } else{ int p = P[ i ][ 0 ] - 'A'; pii v = user2scr_clk[ name[ i ] ]; ftree->update( mp[ v ], -1 ); v.first += 50 * L[ p ] + 500 * L[ p ] / ( 8 + 2 * ++prob_ac_cnt[ p ] ); v.second = -i; user2scr_clk[ name[ i ] ] = v; ftree->update( mp[ v ], 1 ); } } } signed main(){ ios::sync_with_stdio( 0 ); init(); preprocess(); solve(); return 0; }