Submission #58833
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 | //include//------------------------------------------#include <vector>#include <list>#include <map>#include <unordered_map>#include <climits>#include <set>#include <unordered_set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <ctime>#include <queue>#include <random>#include <chrono>#include <complex>#include <regex>#include <locale>#include <random>#include <cassert>#include <type_traits>using namespace std;// typedef//------------------------------------------typedef long long LL;typedef vector<int> VI;typedef vector<bool> VB;typedef vector<char> VC;typedef vector<double> VD;typedef vector<string> VS;typedef vector<LL> VLL;typedef vector<VI> VVI;typedef vector<VB> VVB;typedef vector<VS> VVS;typedef vector<VLL> VVLL;typedef vector<VVI> VVVI;typedef vector<VVLL> VVVLL;typedef pair<int, int> PII;typedef pair<LL, LL> PLL;typedef pair<int, string> PIS;typedef pair<string, int> PSI;typedef pair<string, string> PSS;typedef vector<PII> VPII;typedef vector<PLL> VPLL;typedef vector<VPII> VVPII;typedef vector<VPLL> VVPLL;typedef vector<VS> VVS;typedef map<int, int> MII;typedef map<LL, LL> MLL;typedef map<string, int> MSI;typedef map<int, string> MIS;// container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define SZ(a) int((a).size())#define EACH(i, arr) for(typeof((arr).begin()) i=(arr).begin(); i!=(arr).end(); ++i)#define EXIST(str, e) ((str).find(e)!=(str).end())#define COUNT(arr, v) count((arr).begin(), (arr).end(), v)#define SEARCH(v, w) search((v).begin(), (v).end(), (w).begin(), (w).end())#define SORT(c) sort((c).begin(),(c).end())#define RSORT(c) sort((c).rbegin(),(c).rend())#define REVERSE(c) reverse((c).begin(), (c).end())#define ROTATE_LEFT(arr, c) rotate((arr).begin(), (arr).begin()+(c), (arr).end())#define ROTATE_RIGHT(arr, c) rotate((arr).rbegin(), (arr).rbegin() + (c), (arr).rend())#define SUMI(arr) accumulate((arr).begin(), (arr).end(), 0)#define SUMD(arr) accumulate((arr).begin(), (arr).end(), 0.)#define SUMLL(arr) accumulate((arr).begin(), (arr).end(), 0LL)#define MULD(arr) accumulate((arr).begin(), (arr).end(), 1., multiplies<double>())#define UB(arr, n) upper_bound((arr).begin(), (arr).end(), n)#define LB(arr, n) lower_bound((arr).begin(), (arr).end(), n)#define PB push_back#define MP make_pair#define ft first#define sd second// input output//------------------------------------------#define GL(s) getline(cin, (s))#define INIT() std::ios::sync_with_stdio(false);std::cin.tie(0)#define OUT(d) std::cout<<(d)#define OUT_L(d) std::cout<<(d)<<endl#define FOUT(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data)#define FOUT_L(n, data) std::cout<<std::fixed<<std::setprecision(n)<<(data)<<"\n"#define EL() printf("\n")#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}#define Yes() printf("Yes\n")#define No() printf("No\n")#define YES() printf("YES\n")#define NO() printf("NO\n")#define Yay() printf("Yay!\n")#define Nnn() printf(":(\n")#define CE(x, y) ((x + y - 1) / (y))template<typename T1, typename T2>istream &operator>>(istream &in, pair<T1, T2> &p) { in >> p.first >> p.second; return in;}template<typename T>istream &operator>>(istream &in, vector<T> &v) { for (auto &x: v) in >> x; return in;}template<typename T1, typename T2>ostream &operator<<(ostream &out, const std::pair<T1, T2> &p) { out << "[" << p.first << ", " << p.second << "]" << "\n"; return out;}template<class T1, class T2>inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return true; } return false;}template<class T1, class T2>inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return true; } return false;}//repetition//------------------------------------------#define FOR(i, a, b) for(int i=(a);i<(b);++i)#define RFOR(i, a, b) for(int i=(b)-1;i>=(a);--i)#define REP(i, n) FOR(i,0,n)#define RREP(i, n) for(int i = n-1;i >= 0;i--)#define FORLL(i, a, b) for(LL i=LL(a);i<LL(b);++i)#define RFORLL(i, a, b) for(LL i=LL(b)-1;i>=LL(a);--i)#define REPLL(i, n) for(LL i=0;i<LL(n);++i)#define RREPLL(i, n) for(LL i=LL(n)-1;i>=0;--i)#define FOREACH(x, arr) for(auto &(x) : (arr))//------------------------------------------//------------------------------------------constexpr LL INF = 1e12;int main() { int N; cin >> N; // accumulate small // out large priority_queue<LL> low; // accumulate large // out small priority_queue<LL, VLL, greater<>> high; low.push(-INF); high.push(INF); for (int i = 0; i < N; i++) { LL x; cin >> x; low.push(x); high.push(low.top()); low.pop(); while (high.size() > low.size()) { low.push(high.top()); high.pop(); } while (low.size() > high.size()) { high.push(low.top()); low.pop(); } if (i % 2 == 0) { cout << high.top() << endl; } else { cout << (low.top() + high.top()) / 2 << endl; }; } return 0;} |
ステータス
| 項目 | データ |
|---|---|
| 問題 | 1276 - Median Find |
| ユーザー名 | ganariya |
| 投稿日時 | 2020-03-03 10:49:47 |
| 言語 | C++17 |
| 状態 | Accepted |
| 得点 | 400 |
| ソースコード長 | 5892 Byte |
| 最大実行時間 | 1162 ms |
| 最大メモリ使用量 | 49308 KB |
セット
| セット | 得点 | Cases | |
|---|---|---|---|
| 1 | ALL | 400 / 400 | * |
テストケース
| ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
|---|---|---|---|---|
| in01.txt | AC | 24 ms | 604 KB |
1
|
| in02.txt | AC | 22 ms | 696 KB |
1
|
| in03.txt | AC | 77 ms | 1172 KB |
1
|
| in04.txt | AC | 80 ms | 1208 KB |
1
|
| in05.txt | AC | 194 ms | 2648 KB |
1
|
| in06.txt | AC | 79 ms | 2312 KB |
1
|
| in07.txt | AC | 691 ms | 7840 KB |
1
|
| in08.txt | AC | 23 ms | 4844 KB |
1
|
| in09.txt | AC | 1130 ms | 13880 KB |
1
|
| in10.txt | AC | 1133 ms | 18656 KB |
1
|
| in11.txt | AC | 19 ms | 14760 KB |
1
|
| in12.txt | AC | 17 ms | 14604 KB |
1
|
| in13.txt | AC | 14 ms | 14704 KB |
1
|
| in14.txt | AC | 20 ms | 14680 KB |
1
|
| in15.txt | AC | 17 ms | 14652 KB |
1
|
| in16.txt | AC | 23 ms | 14624 KB |
1
|
| in17.txt | AC | 998 ms | 19812 KB |
1
|
| in18.txt | AC | 1025 ms | 20748 KB |
1
|
| in19.txt | AC | 1014 ms | 21812 KB |
1
|
| in20.txt | AC | 1108 ms | 27100 KB |
1
|
| in21.txt | AC | 1106 ms | 31876 KB |
1
|
| in22.txt | AC | 1162 ms | 36652 KB |
1
|
| in23.txt | AC | 1153 ms | 41428 KB |
1
|
| in24.txt | AC | 1160 ms | 46328 KB |
1
|
| in25.txt | AC | 1061 ms | 49308 KB |
1
|
| sample01.txt | AC | 27 ms | 45276 KB |
1
|
| sample02.txt | AC | 22 ms | 45244 KB |
1
|
| sample03.txt | AC | 19 ms | 45216 KB |
1
|