제출 #1102283

#제출 시각아이디문제언어결과실행 시간메모리
1102283CDuongSwap Swap Sort (CCO21_day1problem1)C++17
6 / 25
5057 ms18268 KiB
/* #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include <bits/stdc++.h> #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define i64 long long #define isz(x) (int)x.size() using namespace std; template<bool ALLOW_NON_PREFIX_QUERY, class T, class F, class I> struct fenwick_tree{ int n; vector<T> data; F TT; T T_id; I Tinv; fenwick_tree(F TT, T T_id, I Tinv): TT(TT), T_id(T_id), Tinv(Tinv){ } fenwick_tree &operator=(const fenwick_tree &fw){ n = fw.n; data = fw.data; } // O(n) void build(int n){ assert(n >= 0); this->n = n; data.assign(n, T_id); } // O(n) void build(int n, T x){ assert(n >= 0); this->n = n; data.assign(n, x); for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]); } // O(n) template<class U> void build(const vector<U> &a){ n = (int)a.size(); data.resize(n); copy(a.begin(), a.end(), data.begin()); for(auto i = 1; i <= n; ++ i) if(i + (i & -i) <= n) data[i + (i & -i) - 1] = TT(data[i + (i & -i) - 1], data[i - 1]); } // O(log(n)) void update(int p, T x){ assert(0 <= p && p < n); for(++ p; p <= n; p += p & -p) data[p - 1] = TT(data[p - 1], x); } // O(log(n)) void set(int p, T x){ update(p, TT(x, Tinv(query(p)))); } // O(log(n)) T prefix(int r) const{ assert(0 <= r && r <= n); T s = T_id; for(; r > 0; r -= r & -r) s = TT(s, data[r - 1]); return s; } // O(log(n)) T query(int l, int r) const{ static_assert(ALLOW_NON_PREFIX_QUERY); assert(0 <= l && l <= r && r <= n); if(l == r) return T_id; T sum_minus = T_id, sum_plus = T_id; for(; l < r; r -= r & -r) sum_plus = TT(sum_plus, data[r - 1]); for(; r < l; l -= l & -l) sum_minus = TT(sum_minus, data[l - 1]); return TT(sum_plus, Tinv(sum_minus)); } // O(log(n)) T query(int p) const{ static_assert(ALLOW_NON_PREFIX_QUERY); return query(p, p + 1); } // O(log(n)) T query_all() const{ return prefix(n); } // pred(sum[0, r)) is T, T, ..., T, F, F, ..., F, returns max r with T // O(log(n)) int max_pref(auto pred) const{ assert(pred(T_id)); int p = 0; T sum = T_id; for(auto i = __lg(n + 1); i >= 0; -- i) if(p + (1 << i) <= n && pred(TT(sum, data[p + (1 << i) - 1]))){ sum = TT(sum, data[p + (1 << i) - 1]); p += 1 << i; } return p; } template<class output_stream> friend output_stream &operator<<(output_stream &out, const fenwick_tree &fw){ out << "{"; for(auto i = 0; i < fw.n; ++ i){ out << fw.query(i); if(i != fw.n - 1) out << ", "; } return out << '}'; } }; template<class T, class F, class I> auto make_fenwick_tree(F TT, T T_id, I Tinv){ return fenwick_tree<true, T, F, I>(TT, T_id, Tinv); } template<class T> auto make_fenwick_tree_sum(){ return fenwick_tree<true, T, plus<>, negate<>>(plus<>(), T{0}, negate<>()); } template<class T> auto make_fenwick_tree_product(){ auto inverse = [](const T &x){ return 1 / x; }; return fenwick_tree<true, T, multiplies<>, decltype(inverse)>(multiplies<>(), T{1}, inverse); } template<class T> auto make_fenwick_tree_min(){ auto TT = [&](const T &x, const T &y)->T{ return min(x, y); }; return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>()); } template<class T> auto make_fenwick_tree_max(){ auto TT = [&](const T &x, const T &y)->T{ return max(x, y); }; return fenwick_tree<false, T, decltype(TT), negate<>>(TT, numeric_limits<T>::max(), negate<>()); } void solve() { int n, k, q; cin >> n >> k >> q; vector<int> a(n), p(n); vector<vector<int>> pos(k); for (int i = 0; i < n; ++i) { cin >> a[i]; pos[--a[i]].emplace_back(i); } iota(all(p), 0); vector<int> qq(q); vector<vector<int>> ntb(n); for (int i = 0; i < q; ++i) { cin >> qq[i]; --qq[i]; ntb[p[qq[i]]].emplace_back(p[qq[i] + 1]); ntb[p[qq[i] + 1]].emplace_back(p[qq[i]]); swap(p[qq[i]], p[qq[i] + 1]); } vector<int> ap(k); iota(all(ap), 0); sort(all(ap), [&](int x, int y) { return isz(pos[x]) > isz(pos[y]); }); auto fw = make_fenwick_tree_sum<int>(); fw.build(n); vector<bool> vis(n); map<pair<int, int>, i64> mp; for (auto val : ap) { vis[val] = true; for (auto idx : pos[val]) { fw.update(idx, 1); } for (auto val2 : ntb[val]) if (not vis[val2]) { i64 cnt = 0; for (auto idx : pos[val2]) { cnt += fw.prefix(idx); } mp[{val2, val}] = cnt; mp[{val, val2}] = 1ll * isz(pos[val]) * isz(pos[val2]) - cnt; // cout << val2 << " " << val << " " << cnt << endl; } for (auto idx : pos[val]) { fw.update(idx, -1); } } i64 cres = 0; for (int i = k - 1; i >= 0; --i) { for (int j = isz(pos[i]) - 1; j >= 0; --j) { cres += fw.prefix(pos[i][j]); fw.update(pos[i][j], 1); } } // cout << cres << endl; iota(all(p), 0); for (int i = 0; i < q; ++i) { int u = p[qq[i]], v = p[qq[i] + 1]; // cout << u << " " << v << endl; cres = cres - mp[{u, v}] + mp[{v, u}]; cout << cres << "\n"; swap(p[qq[i]], p[qq[i] + 1]); } } signed main() { #ifndef CDuongg if (fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl; #endif }

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

Main.cpp:84:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   84 |     int max_pref(auto pred) const{
      |                  ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...