結果
問題 | No.449 ゆきこーだーの雨と雪 (4) |
ユーザー |
![]() |
提出日時 | 2016-11-19 07:22:22 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 234 ms / 5,000 ms |
コード長 | 2,661 bytes |
コンパイル時間 | 918 ms |
コンパイル使用メモリ | 78,288 KB |
実行使用メモリ | 17,792 KB |
最終ジャッジ日時 | 2024-09-22 10:24:13 |
合計ジャッジ時間 | 9,793 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 43 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 63 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:64:26: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 64 | inc(i, n) { scanf("%d", &l[i]); } | ~~~~~^~~~~~~~~~~~~ main.cpp:65:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 65 | scanf("%d", &t); | ~~~~~^~~~~~~~~~
ソースコード
#include <cstdio>#include <cmath>#include <iostream>#include <string>#include <map>#include <set>#include <algorithm>#define incID(i, l, r) for(int i = (l) ; i < (r); i++)#define incII(i, l, r) for(int i = (l) ; i <= (r); i++)#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)#define decII(i, l, r) for(int i = (r) ; i >= (l); i--)#define inc( i, n) incID(i, 0, n)#define inc1(i, n) incII(i, 1, n)#define dec( i, n) decID(i, 0, n)#define dec1(i, n) decII(i, 1, n)typedef long long signed int LL;typedef long long unsigned int LU;template<typename T> void swap(T &x, T &y) { T t = x; x = y; y = t; return; }template<typename T> T abs(T x) { return (0 <= x ? x : -x); }template<typename T> T max(T a, T b) { return (b <= a ? a : b); }template<typename T> T min(T a, T b) { return (a <= b ? a : b); }template<typename T> bool setmin(T &a, T b) { if(a <= b) { return false; } else { a = b; return true; } }template<typename T> bool setmax(T &a, T b) { if(b <= a) { return false; } else { a = b; return true; } }template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }// ---- ----int n, l[26], t;int ac[26], counter, score[100000], at[100000];std::map<std::string, int> m;struct Node { int right_num, left, right; };class Tree {Node node[31 * 100000];int ptr = 1;public:void insert(int v) { search(v, 1); }void erase(int v) { search(v, -1); }int find(int v) { return search(v, 0); }int search(int v, int diff);};int Tree::search(int v, int diff) {int r[32], rank = 0;r[0] = 0;inc(i, 31) {bool is_left = ((v & (1 << (30 - i))) == 0);if(is_left) { rank += node[ r[i] ].right_num; } else { node[ r[i] ].right_num += diff; }int & rr = (is_left ? node[ r[i] ].left : node[ r[i] ].right);if(rr == 0) { rr = ptr++; }r[i + 1] = rr;}return rank;}Tree v;int main() {scanf("%d", &n);inc(i, n) { scanf("%d", &l[i]); }scanf("%d", &t);inc(i, t) {std::string name;char p;std::cin >> name >> p;if(p != '?') {auto it = m.find(name);bool new_flag = (it == m.end());if(new_flag) {it = (m.insert(std::make_pair(name, counter++))).first;}int id = it -> second;int prob = p - 'A';ac[prob]++;int plus = ( 50 * l[prob] + (500 * l[prob]) / (8 + 2 * ac[prob]) ) * 100001 + at[id] - i;at[id] = i;if(new_flag) {v.insert(plus);} else {v.erase(score[id]);v.insert(score[id] + plus);}score[id] += plus;} else {int id = m.find(name) -> second;printf("%d\n", v.find(score[id]) + 1);}}return 0;}