結果
問題 | No.318 学学学学学 |
ユーザー |
![]() |
提出日時 | 2017-12-15 00:33:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#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<<endltypedef 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;}