제출 #877078

#제출 시각아이디문제언어결과실행 시간메모리
877078raul2008487Arranging Shoes (IOI19_shoes)C++17
100 / 100
197 ms14240 KiB
#include "shoes.h" #include<bits/stdc++.h> #define ll long long #define pb push_back #define all(v) v.begin(), v.end() #define fi first #define se second #define in insert using namespace std; const int sz = 2e5+5; ll Tree[sz]; void add(ll pos, ll val){ for(ll i = pos; i<sz ; i += (i & (-i))){ Tree[i] += val; } } ll get(ll pos){ ll rx = 0; for(ll i = pos; i>0; i -= (i & (-i))){ rx += Tree[i]; } return rx; } ll ask(ll l, ll r){ return get(r) - get(l-1); } long long count_swaps(vector<int> s) { ll n = s.size(), ans = 0; set<pair<int,int>> c; for(ll i=0;i<n;i++){ c.in({s[i], i}); add(i+1, 1); } for(ll i=0;i<n;i++){ if(c.find({s[i], i}) == c.end()){continue;} ll ix = (*c.lower_bound({-s[i], i})).se; if(ix >= (i+2)){ ans += ask(i+2, ix); } if(s[i] > 0){ ans++; } add(i+1, -1); add(ix+1, -1); c.erase({s[i], i}); c.erase({-s[i], ix}); } 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...