제출 #713998

#제출 시각아이디문제언어결과실행 시간메모리
713998europiumArranging Shoes (IOI19_shoes)C++17
100 / 100
639 ms150112 KiB
#include "shoes.h" #include <cstdio> #include <cassert> #include <iostream> #include <vector> #include <algorithm> #include <string> #include <numeric> #include <cmath> #include <iterator> #include <set> #include <map> #include <math.h> #include <iomanip> #include <queue> #include <unordered_set> using namespace std; using ll = long long; struct segtree{ int size; vector <int> values; int NEUTRAL_ELEMENT = 0; int merge(int a, int b){ return a + b; } void init(int n){ size = 1; while (size < n) size *= 2; values.resize(2 * size, 0); } void build(vector<int> &a, int x, int lx, int rx){ if (rx - lx == 1){ if (lx < a.size()){ values[x] = a[lx]; } return; } int m = (lx + rx) / 2; build(a, 2 * x + 1, lx, m); build(a, 2 * x + 2, m, rx); values[x] = merge(values[2 * x + 1], values[2 * x + 2]); } void build(vector<int> &a){ build(a, 0, 0, size); } void set(int i, int v, int x, int lx, int rx){ if (rx - lx == 1){ values[x] = v; return; } int m = (lx + rx) / 2; if (i < m){ set(i, v, 2 * x + 1, lx, m); } else{ set(i, v, 2 * x + 2, m, rx); } values[x] = merge(values[2 * x + 1], values[2 * x + 2]); } void set(int i, int v){ set(i, v, 0, 0, size); } int calc(int l, int r, int x, int lx, int rx){ if (lx >= r || l >= rx) return NEUTRAL_ELEMENT; if (lx >= l && rx <= r) return values[x]; int m = (lx + rx) / 2; int s1 = calc(l, r, 2 * x + 1, lx, m); int s2 = calc(l, r, 2 * x + 2, m, rx); return merge(s1, s2); } int calc(int l, int r){ return calc(l, r, 0, 0, size); } }; ll count_swaps(vector<int> a) { ll n = a.size(); ll ans = 0; segtree st; st.init(n); vector<int> used(n, 1); st.build(used); map<int,queue<int>> pos; for (int i = 0; i < n; i++){ pos[a[i]].push(i + 1); } for (ll i = 0; i < n; i++){ if (used[i] == 0) continue; int j = pos[-a[i]].front() - 1; pos[-a[i]].pop(); pos[a[i]].pop(); st.set(i, 0); st.set(j, 0); used[i] = 0; used[j] = 0; int val = st.calc(i, j); if (a[i] > 0) ans += val + 1; else ans += val; } return ans; }

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

shoes.cpp: In member function 'void segtree::build(std::vector<int>&, int, int, int)':
shoes.cpp:39:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             if (lx < a.size()){
      |                 ~~~^~~~~~~~~~
#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...