結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2017-12-15 00:33:50 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 1,965 bytes |
コンパイル時間 | 1,583 ms |
コンパイル使用メモリ | 183,132 KB |
実行使用メモリ | 18,432 KB |
最終ジャッジ日時 | 2024-06-22 18:23:46 |
合計ジャッジ時間 | 5,302 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 11 ms
6,816 KB |
testcase_01 | AC | 24 ms
6,816 KB |
testcase_02 | AC | 29 ms
6,944 KB |
testcase_03 | AC | 19 ms
6,940 KB |
testcase_04 | AC | 26 ms
6,940 KB |
testcase_05 | AC | 171 ms
18,432 KB |
testcase_06 | AC | 191 ms
14,080 KB |
testcase_07 | AC | 150 ms
10,880 KB |
testcase_08 | AC | 120 ms
8,192 KB |
testcase_09 | AC | 98 ms
6,940 KB |
testcase_10 | AC | 68 ms
6,940 KB |
testcase_11 | AC | 167 ms
18,432 KB |
testcase_12 | AC | 167 ms
13,824 KB |
testcase_13 | AC | 123 ms
10,752 KB |
testcase_14 | AC | 91 ms
8,192 KB |
testcase_15 | AC | 70 ms
6,944 KB |
testcase_16 | AC | 52 ms
6,940 KB |
testcase_17 | AC | 131 ms
14,080 KB |
testcase_18 | AC | 104 ms
13,824 KB |
testcase_19 | AC | 126 ms
13,952 KB |
testcase_20 | AC | 35 ms
6,940 KB |
testcase_21 | AC | 2 ms
6,944 KB |
testcase_22 | AC | 2 ms
6,940 KB |
testcase_23 | AC | 2 ms
6,940 KB |
testcase_24 | AC | 1 ms
6,940 KB |
testcase_25 | AC | 2 ms
6,940 KB |
testcase_26 | AC | 2 ms
6,940 KB |
testcase_27 | AC | 2 ms
6,944 KB |
testcase_28 | AC | 2 ms
6,944 KB |
ソースコード
#include "bits/stdc++.h" using namespace std; #define DEBUG(x) cout<<#x<<": "<<x<<endl; #define DEBUG_VEC(v) cout<<#v<<":";for(int i=0;i<v.size();i++) cout<<" "<<v[i]; cout<<endl typedef long long ll; #define vi vector<int> #define vl vector<ll> #define vii vector< vector<int> > #define vll vector< vector<ll> > #define vs vector<string> #define pii pair<int,int> #define pis pair<int,string> #define psi pair<string,int> #define pll pair<ll,ll> const int inf = 1000000001; const ll INF = 1e18 * 2; #define MOD 1000000007 #define mod 1000000009 #define pi 3.14159265358979323846 #define Sp(p) cout<<setprecision(15)<< fixed<<p<<endl; int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; int main() { int n; cin >> n; int i, j; vi a(n); map<int, int> left, right; set<int> st; for (i = 0; i < n; i++) { cin >> a[i]; st.insert(a[i]); if (left[a[i]] == 0) { left[a[i]] = i + 1; } else { right[a[i]] = i + 1; } } vi b(n); for (auto itr = st.begin(); itr != st.end(); itr++) { int x = *itr; if (right[x]) { int l = left[x] - 1, r = right[x] - 1; b[l] = b[r] = x; } else { int l = left[x] - 1; b[l] = -x; } } //DEBUG_VEC(b); map<int, int> state; priority_queue<int> pq; vi ans(n); int now = -1; for (i = 0; i < n; i++) { if (b[i]) { int x = b[i]; if (x < 0) { if (now < abs(x)) { ans[i] = abs(x); } else { ans[i] = now; } continue; } if (state[x] == 0) { state[x]++; if (now < x) { pq.push(now); now = x; } else { pq.push(x); } ans[i] = now; } else if (state[x] == 1) { state[x]++; ans[i] = now; if (now == x) { now = pq.top(); pq.pop(); while (state[now] == 2) { now = pq.top(); pq.pop(); } } } } else { ans[i] = now; } } for (i = 0; i < n; i++) { cout << ans[i] << " "; } cout << endl; }