제출 #810201

#제출 시각아이디문제언어결과실행 시간메모리
810201NothingXDArranging Shoes (IOI19_shoes)C++17
100 / 100
60 ms19172 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef double ld; void debug_out(){cerr<<endl;} template<typename Head, typename... Tail> void debug_out(Head H, Tail... T){ cerr << H << ' '; debug_out(T...); } #define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__) #define F first #define S second #define all(x) x.begin(), x.end() #define MP(x, y) make_pair(x, y) const int maxn = 2e5 + 10; int n, f[maxn]; vector<int> idx[maxn][2]; bool mark[maxn]; void add(int idx, int x){ for (; idx <= n; idx += idx & -idx) f[idx] += x; } int get(int idx){ int res = 0; for (; idx; idx -= idx & -idx) res += f[idx]; return res; } ll count_swaps(vector<int> s) { n = s.size(); for (int i = 0; i < n; i++){ add(i+1, 1); if (s[i] < 0) idx[-s[i]][0].push_back(i); else idx[s[i]][1].push_back(i); mark[i] = true; } for (int i = 1; i <= n; i++){ reverse(all(idx[i][0])); reverse(all(idx[i][1])); } ll ans = 0; for (int i = 0; i < n; i++){ if (!mark[i]) continue; mark[i] = false; if (s[i] > 0) ans++; int ptr = abs(s[i]); int ptr2 = (s[i] > 0? 1: 0); add(i+1, -1); idx[ptr][ptr2].pop_back(); ans += get(idx[ptr][1-ptr2].back()); add(idx[ptr][1-ptr2].back()+1, -1); mark[idx[ptr][1-ptr2].back()] = false; idx[ptr][1-ptr2].pop_back(); } return ans; }
#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...