제출 #494638

#제출 시각아이디문제언어결과실행 시간메모리
494638aryan12중앙값 배열 (balkan11_medians)C++17
100 / 100
139 ms17416 KiB
#include <bits/stdc++.h> using namespace std; #define int long long mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); const int N = 2e5 + 5; int seg[N * 4]; void Upd(int l, int r, int pos, int qpos) { if(l == r) { seg[pos]++; return; } int mid = (l + r) >> 1; if(qpos <= mid) Upd(l, mid, pos * 2, qpos); else Upd(mid + 1, r, pos * 2 + 1, qpos); seg[pos] = seg[pos * 2] + seg[pos * 2 + 1]; } int Query(int l, int r, int pos, int ql, int qr) { if(ql <= l && r <= qr) { return seg[pos]; } if(ql > r || l > qr) { return 0; } int mid = (l + r) >> 1; return Query(l, mid, pos * 2, ql, qr) + Query(mid + 1, r, pos * 2 + 1, ql, qr); } void Solve() { int n; cin >> n; int b[n + 1]; for(int i = 1; i <= n; i++) { cin >> b[i]; } int a[n * 2 + 1]; set<int> s; for(int i = 1; i < 2 * n; i++) { s.insert(i); } for(int i = 1; i < n * 2; i++) { a[i] = 0; } vector<int> ans; ans.push_back(b[1]); a[b[1]] = 1; s.erase(b[1]); /*for(auto i: s) { cout << i << " "; } cout << endl;*/ //cout << "first val = " << b[1] << endl; Upd(1, 2 * n - 1, 1, b[1]); for(int i = 2; i <= n; i++) { //cout << "i = " << i << endl; if(a[b[i]] == 1) { int ans1 = Query(1, 2 * n - 1, 1, 1, b[i] - 1), ans2 = Query(1, 2 * n - 1, 1, b[i] + 1, 2 * n - 1); assert(ans1 - ans2 == -2 || ans1 - ans2 == 0 || ans1 - ans2 == 2); //cout << "ans1 = " << ans1 << ", ans2 = " << ans2 << "\n"; int st = ((ans1 - ans2) == -2) ? 2 : ((ans1 - ans2 == 0) ? 1 : 0); int en = ((ans1 - ans2) == 2) ? 2 : ((ans1 - ans2 == 0) ? 1 : 0); while(st != 0) { //cout << "hey" << endl; assert(s.size() != 0); /*for(auto j: s) { cout << j << " "; } cout << endl;*/ //cout << "ok" << endl; /*for(auto j: s) { cout << j << " "; }*/ //cout << endl; auto f = s.begin(); //cout << "bro " << *f << endl; int x = *f; s.erase(*f); //cout << "omg " << *(f) << endl; ans.push_back(x); //cout << ans[ans.size() - 1] << "\n"; //cout << (*f) << endl; //cout << "ok" << endl; a[x] = 1; //cout << "omk" << endl; Upd(1, 2 * n - 1, 1, x); //cout << "val = " << *f << endl; st--; /*for(auto j: s) { cout << j << " "; } cout << endl;*/ } while(en != 0) { //cout << "hey" << endl; assert(s.size() != 0); auto f = --s.end(); int x = *f; s.erase(*f); ans.push_back(x); a[x] = 1; Upd(1, 2 * n - 1, 1, x); //cout << "value = " << *f << endl; en--; } } else { ans.push_back(b[i]); a[b[i]] = 1; //cout << "Upd value = " << b[i] << endl; s.erase(b[i]); Upd(1, 2 * n - 1, 1, b[i]); int ans1 = Query(1, 2 * n - 1, 1, 1, b[i] - 1), ans2 = Query(1, 2 * n - 1, 1, b[i] + 1, 2 * n - 1); assert(abs(ans1 - ans2) == 1); if(ans1 < ans2) { assert(s.size() != 0); auto f = s.begin(); int x = *f; s.erase(*f); ans.push_back(x); a[x] = 1; //cout << "Val = " << *f << endl; Upd(1, 2 * n - 1, 1, x); } else { assert(s.size() != 0); auto f = --s.end(); int x = *f; s.erase(*f); ans.push_back(x); a[x] = 1; //cout << "Value = " << *f << endl; Upd(1, 2 * n - 1, 1, x); } } /*for(auto j: s) { cout << j << " "; } cout << endl;*/ } assert(s.size() == 0); for(int i = 0; i < ans.size(); i++) { cout << ans[i] << " "; } cout << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; //cin >> t; while(t--) { Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

medians.cpp: In function 'void Solve()':
medians.cpp:144:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for(int i = 0; i < ans.size(); i++) {
      |                 ~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...