제출 #403167

#제출 시각아이디문제언어결과실행 시간메모리
403167SavicSArranging Shoes (IOI19_shoes)C++14
100 / 100
154 ms33656 KiB
#include "shoes.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define ff(i,a,b) for(int i=a;i<=b;i++) #define fb(i,b,a) for(int i=b;i>=a;i--) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef pair<int,int> pii; const int maxn = 200005; const int inf = 1e9 + 5; template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // os.order_of_key(k) the number of elements in the os less than k // *os.find_by_order(k) print the k-th smallest number in os(0-based) int n; int niz[maxn]; set<int> poz[maxn]; set<int> neg[maxn]; ll dud[maxn]; void upd(int x, ll val){ while(x <= maxn){ dud[x] += val; x += x&(-x); } } ll query(int x){ ll sum = 0; while(x > 0){ sum += dud[x]; x -= x&(-x); } return sum; } ll count_swaps(vector<int> S){ n = sz(S); ff(i,0,n - 1)niz[i + 1] = S[i]; ff(i,1,n){ if(niz[i] < 0)neg[-niz[i]].insert(i); else poz[niz[i]].insert(i); upd(i, 1); } ll rez = 0; ff(i,1,n){ int X = niz[i]; if(X < 0 && neg[-X].count(i) == 0)continue; if(X > 0 && poz[X].count(i) == 0)continue; if(X < 0){ auto a = poz[-X].begin(); poz[-X].erase(a), neg[-X].erase(i); rez += query(*a) - query(i) - 1; upd(i, 1), upd(*a + 1, -1); } else{ auto a = neg[X].begin(); neg[X].erase(a), poz[X].erase(i); rez += query(*a) - query(i); upd(i, 1), upd(*a + 1, -1); } } return rez; } //int main() //{ // ios::sync_with_stdio(false); // cout.tie(nullptr); // cin.tie(nullptr); // cin >> n; // vector<int> a(n); // ff(i,0,n - 1)cin >> a[i]; // // cout << count_swaps(a) << endl; // // return 0; //} /** 4 2 1 -1 -2 6 -2 2 2 -2 -2 2 4 -2 -1 2 1 // probati bojenje sahovski ili slicno **/
#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...