제출 #66458

#제출 시각아이디문제언어결과실행 시간메모리
66458zadrgaBubble Sort 2 (JOI18_bubblesort2)C++14
60 / 100
203 ms30152 KiB
#include "bubblesort2.h" #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second #define INF (int) (2 * 1e9) #define MOD (1000 * 1000 * 1000 + 7) #define maxn 200111 typedef long long ll; typedef long double ld; typedef pair<int, int> pii; struct segtree{ int seg[4 * maxn], lazy[4 * maxn]; void push(int x, int l, int d){ seg[x] += lazy[x]; if(l != d){ lazy[2 * x] += lazy[x]; lazy[2 * x + 1] += lazy[x]; } lazy[x] = 0; } void update(int x, int l, int d, int i, int j, int val){ push(x, l, d); if(l > d || l > j || d < i) return; if(i <= l && d <= j){ lazy[x] += val; push(x, l, d); return; } int mid = (l + d) / 2; update(2 * x, l, mid, i, j, val); update(2 * x + 1, mid + 1, d, i, j, val); seg[x] = max(seg[2 * x], seg[2 * x + 1]); } int get(int x, int l, int d){ push(x, l, d); return seg[x]; } } seg; int arr[maxn]; int n; void remove(int x, int pos){ seg.update(1, 1, n, x, x, -(INF + pos)); seg.update(1, 1, n, x + 1, n, 1); } void add(int x, int pos){ seg.update(1, 1, n, x, x, INF + pos); seg.update(1, 1, n, x + 1, n, -1); } vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){ vector<int> ans; int q = X.size(); vector<pii> v; for(int i = 0; i < A.size(); i++) v.pb(mp(A[i], i)); for(int i = 0; i < q; i++) v.pb(mp(V[i], X[i])); sort(v.begin(), v.end()); v.resize(distance(v.begin(), unique(v.begin(), v.end()))); n = v.size(); seg.update(1, 1, n, 1, n, -INF); for(int i = 0; i < A.size(); i++){ A[i] = lower_bound(v.begin(), v.end(), mp(A[i], i)) - v.begin() + 1; add(A[i], i); arr[i] = A[i]; } for(int i = 0; i < q; i++){ V[i] = lower_bound(v.begin(), v.end(), mp(V[i], X[i])) - v.begin() + 1; int pos = X[i]; remove(arr[pos], pos); add(V[i], pos); arr[pos] = V[i]; ans.pb(seg.get(1, 1, n)); } return ans; } /* 4 2 1 2 3 4 0 3 2 1 */

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

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:72:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < A.size(); i++)
                 ~~^~~~~~~~~~
bubblesort2.cpp:84:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < A.size(); i++){
                 ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...