제출 #264194

#제출 시각아이디문제언어결과실행 시간메모리
264194hamerinArranging Shoes (IOI19_shoes)C++17
100 / 100
176 ms8948 KiB
#include "shoes.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed const size_t fTsize = 1 << 18; class fenwickTree { public: vector<int> vl; int N; fenwickTree() { vl.resize(fTsize); } int query(int t) { int ret = 0; while (t) ret += vl[t], t -= (t & -t); return ret; } int query(int l, int r) { return query(r) - query(l - 1); } void update(int t, int d = -1) { while (t < fTsize) vl[t] += d, t += (t & -t); } }; i64 count_swaps(vector<int> s) { int N = s.size() >> 1; i64 ret = 0; set<pi> st; vector<pi> match; for (int i = 0; i < 2 * N; i++) { auto it = st.lower_bound({-s[i], 0}); if (it != st.end() && it->first == -s[i]) { match.emplace_back(it->second, i); st.erase(it); } else { st.insert({s[i], i}); } } sort(iterall(match)); auto fT = fenwickTree(); for (int i = 1; i <= 2 * N; i++) fT.update(i, 1); for (auto [l, r] : match) { ret += fT.query(++l, ++r); ret -= 2; if (s[l - 1] > s[r - 1]) ret += 1; fT.update(l); fT.update(r); } return ret; }

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

shoes.cpp: In member function 'void fenwickTree::update(int, int)':
shoes.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'const size_t' {aka 'const long unsigned int'} [-Wsign-compare]
   37 |         while (t < fTsize) vl[t] += d, t += (t & -t);
      |                ~~^~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...