제출 #235946

#제출 시각아이디문제언어결과실행 시간메모리
235946triple_faultArranging Shoes (IOI19_shoes)C++14
50 / 100
1104 ms226040 KiB
#include "shoes.h" #include <set> #include <cstdio> #include <algorithm> #include <cstring> #define ll long long #define mid ((tl + tr) / 2) #define lft (v * 2) #define rht ((v * 2) + 1) #define MAX 200000 using namespace std; ll n; vector<ll> shoes(MAX); struct segtree { segtree* left = NULL; segtree* right = NULL; multiset<ll> here; ll m_tl, m_tr; bool inactive = true; ll sum_here = 0; void build(ll tl, ll tr) { m_tl = tl, m_tr = tr; if (tl == tr) { here.insert(shoes[tl]); inactive = false; return; } left = new segtree(); right = new segtree(); left->build(tl, mid); right->build(mid + 1, tr); merge(left->here.begin(), left->here.end(), right->here.begin(), right->here.end(), inserter(here, here.begin())); } ll query(ll needle) { here.erase(here.find(needle)); ++sum_here; if (m_tl == m_tr) { inactive = true; return m_tl; } if (left->here.find(needle) != left->here.end()) return left->query(needle); else if (right->here.find(needle) != right->here.end()) return right->query(needle); else puts("fuck this"); return MAX * MAX; } ll sum(ll tl, ll tr) { if (tl > tr) return 0; if (tl == m_tl && tr == m_tr) return sum_here; return left->sum(tl, min(tr, (m_tl + m_tr) / 2)) + right->sum(max(tl, ((m_tl + m_tr) / 2) + 1), tr); } } segtree; long long count_swaps(std::vector<int> s) { ll n = s.size(); for (ll i = 0; i < n; ++i) shoes[i] = (ll)s[i]; segtree.build(0, n - 1); ll inactive_a[n]; memset(inactive_a, 0, sizeof inactive_a); ll ans = 0; for (ll i = 0; i < n; ++i) { if (inactive_a[i]) continue; segtree.query(shoes[i]); ll nxt = -shoes[i]; ll q = segtree.query(nxt); ans += (q - i - 1 - segtree.sum(i + 1, q - 1)); if (nxt < 0) ++ans; inactive_a[i] = 1; inactive_a[q] = 1; } return ans; }

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

shoes.cpp: In member function 'long long int segtree::query(long long int)':
shoes.cpp:56:20: warning: integer overflow in expression [-Woverflow]
         return MAX * MAX;
                    ^
#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...