제출 #1070779

#제출 시각아이디문제언어결과실행 시간메모리
1070779dostsArranging Shoes (IOI19_shoes)C++17
100 / 100
77 ms20436 KiB
//Dost SEFEROĞLU #include <bits/stdc++.h> #include "shoes.h" using namespace std; #define int long long #define pii pair<int,int> #define ff first #define ss second #define sp << " " << #define all(cont) cont.begin(),cont.end() #define vi vector<int> const int MOD = 1e9+7,inf = 2e18; const int N = 1e5+50; struct FT { int n; vi bit; FT(int nn) { n = nn; bit.assign(n+1,0); } int get(int p) { int ans = 0; for (int i=p;i>0;i-=i&-i) ans += bit[i]; return ans; } void put(int p,int v) { for (int i=p;i<=n;i+=i&-i) bit[i]+=v; } }; long long count_swaps(std::vector<int32_t> s) { int n = s.size(); FT ft(n); for (int i=1;i<=n;i++) ft.put(i,1); int sm = 0; vi pos[n+1]; for (int i=1;i<=n;i++) pos[abs(s[i-1])].push_back(i); for (int i=1;i<=n;i++) { stack<int> left,right; for (auto it : pos[i]) { if (s[it-1] > 0) right.push(it); else left.push(it); if (!left.empty() && !right.empty()) { int a = left.top(),b = right.top(); if (a > b) { sm++; s[a-1] = -s[a-1]; s[b-1] = -s[b-1]; } left.pop(),right.pop(); } } } vi rights[n+1]; for (int i=1;i<=n;i++) if (s[i-1] > 0) rights[s[i-1]].push_back(i); for (int i=1;i<=n;i++) reverse(all(rights[i])); for (int i=1;i<=n;i++) { if (s[i-1] < 0) { int nxt = rights[-s[i-1]].back(); rights[-s[i-1]].pop_back(); sm+=ft.get(nxt)-ft.get(i)-1; ft.put(nxt,-1); } } return sm; }
#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...