제출 #143558

#제출 시각아이디문제언어결과실행 시간메모리
143558abekerArranging Shoes (IOI19_shoes)C++17
100 / 100
282 ms35704 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 2e5 + 5; struct fenwick { vector <int> fen; fenwick(int n) { fen.resize(n + 5); } void update(int x, int val) { for (x++; x < fen.size(); x += x & -x) fen[x] += val; } int get(int x) { int res = 0; for (x++; x; x -= x & -x) res += fen[x]; return res; } }; int N; vector <int> lft[MAXN], rig[MAXN]; vector <int> perm[MAXN], pos[MAXN]; ll inversions(vector <int> v) { reverse(v.begin(), v.end()); fenwick tmp(v.size()); ll res = 0; for (auto it : v) { res += tmp.get(it); tmp.update(it, 1); } return res; } ll count_swaps(vector <int> shoes) { N = shoes.size(); vector <int> todo(N, -1); for (int i = 0; i < N; i++) { int sz = abs(shoes[i]); if (shoes[i] < 0) { perm[sz].push_back(2 * lft[sz].size()); lft[sz].push_back(i); } else { perm[sz].push_back(2 * rig[sz].size() + 1); rig[sz].push_back(i); } pos[sz].push_back(i); } ll sol = 0; for (int i = 0; i < N; i++) { sol += inversions(perm[i]); for (int j = 0; j < lft[i].size(); j++) todo[max(lft[i][j], rig[i][j])] = min(lft[i][j], rig[i][j]); } fenwick fin(N); for (int i = 0; i < N; i++) if (todo[i] != -1) { sol += fin.get(N) - fin.get(todo[i]); fin.update(todo[i], 1); fin.update(i, 1); } fenwick sub(N); for (int i = 0; i < N; i++) { for (auto it : pos[i]) if (todo[it] != -1) { sol -= sub.get(N) - sub.get(todo[it]); sub.update(todo[it], 1); sub.update(it, 1); } for (auto it : pos[i]) if (todo[it] != -1) { sub.update(todo[it], -1); sub.update(it, -1); } } return sol; }

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

shoes.cpp: In member function 'void fenwick::update(int, int)':
shoes.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (x++; x < fen.size(); x += x & -x)
             ~~^~~~~~~~~~~~
shoes.cpp: In function 'll count_swaps(std::vector<int>)':
shoes.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < lft[i].size(); j++) 
                   ~~^~~~~~~~~~~~~~~
#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...