제출 #1186811

#제출 시각아이디문제언어결과실행 시간메모리
1186811hamzabcArranging Shoes (IOI19_shoes)C++20
100 / 100
229 ms20764 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() #define sp << " " << class segtre{ private: int sz; vector<int> tre; void _update(int x, int d, int l, int r, int s){ if (l > x || r < x) return; if (l == r){ tre[s] += d; return; } int m = (l + r) >> 1; _update(x, d, l, m, s << 1); _update(x, d, m + 1, r, (s << 1) | 1); tre[s] = tre[s << 1] + tre[(s << 1) | 1]; } int _query(int tl, int tr, int l, int r, int s){ if (l > tr || r < tl) return 0; if (tl <= l && r <= tr){ return tre[s]; } int m = (l + r) >> 1; return _query(tl, tr, l, m, s << 1) + _query(tl, tr, m + 1, r, (s << 1) | 1); } public: void init(int size){ sz = size; tre.resize(size * 4); } void update(int konum, int add){ _update(konum, add, 0, sz - 1, 1); } int query(int l, int r){ return _query(l, r, 0, sz - 1, 1); } }; long long count_swaps(std::vector<int> s) { segtre tre; int n = s.size(); tre.init(n); map<int, vector<int>> zip; int j = 1; for (int i = 0; i < n; i++){ if (s[i] < 0) continue; zip[-s[i]].push_back(-j); s[i] = j; j++; } for (int i = n - 1; i >= 0; i--){ if (s[i] > 0) continue; int tmp = s[i]; s[i] = zip[tmp].back(); zip[tmp].pop_back(); } long long int ret = 0; map<int, int> mp; for (int i = 0; i < n; i++){ if (mp[abs(s[i])]){ ret += i - mp[abs(s[i])]; if (s[i] < 0) ret += 1; tre.update(i, -1); mp[abs(s[i])] = i; }else{ mp[abs(s[i])] = i + 1; tre.update(i, 1); } } for (int i = 0; i < n; i++){ if (s[i] == 0) continue; ret -= tre.query(i, mp[abs(s[i])]); // tre.update(i, -1); // this doesn't needed tre.update(mp[abs(s[i])], 1); s[mp[abs(s[i])]] = 0; } return ret; }
#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...