제출 #661144

#제출 시각아이디문제언어결과실행 시간메모리
661144amsramanArranging Shoes (IOI19_shoes)C++17
45 / 100
43 ms10544 KiB
#include <bits/stdc++.h> typedef long long ll; using namespace std; template <typename T> struct FenwickTree { size_t n; vector<T> bit; FenwickTree(size_t n): n(n), bit(n, 0) {}; FenwickTree(vector<T> & init): n((int) init.size()), bit((int) init.size()) { copy(init.begin(), init.end(), bit.begin()); for(int i = 1; i <= n; i++) { if(i + (i & -i) <= n) { bit[i + (i & -i) - 1] += bit[i - 1]; } } } T qry(int k) { T ret = 0; for(k++; k > 0; k -= k & -k) { ret += bit[k - 1]; } return ret; } T qry(int l, int r) { return qry(r) - qry(l - 1); } void upd(int k, T x) { for(k++; k <= n; k += k & -k) { bit[k - 1] += x; } } }; ll count_swaps(vector<int> S) { int n = S.size(); ll ans = 0; FenwickTree<ll> ft(n); vector<int> lefts; vector<vector<int>> rights(n / 2); for(int i = 0; i < n; i++) { ft.upd(i, 1); if(S[i] < 0) { lefts.push_back(i); } else { rights[S[i] - 1].push_back(i); } } for(int i = 0; i < n / 2; i++) { reverse(rights[i].begin(), rights[i].end()); } for(int i = 0; i < n / 2; i++) { ft.upd(lefts[i], -1); ans += ft.qry(lefts[i]); int pos = -S[lefts[i]] - 1, right_back = rights[pos].back(); rights[pos].pop_back(); ft.upd(right_back, -1); ans += ft.qry(right_back); } return ans; }

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

shoes.cpp: In instantiation of 'void FenwickTree<T>::upd(int, T) [with T = long long int]':
shoes.cpp:43:20:   required from here
shoes.cpp:30:20: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for(k++; k <= n; k += k & -k) {
      |                  ~~^~~~
#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...