Submission #311281

#TimeUsernameProblemLanguageResultExecution timeMemory
311281saarang123Arranging Shoes (IOI19_shoes)C++14
50 / 100
278 ms274044 KiB
#include "bits/stdc++.h" using namespace std; using ll = long long; const int N = 2e5 + 2; int tree[N], n; queue<int> l[N], r[N]; void upd(int x, int val) { for(; x <= n; x += (x & -x)) tree[x] += val; } int sum(int x) { if(x <= 0) return 0; int ans = 0; for(; x > 0; x -= (x & -x)) ans += tree[x]; return ans; } int qry(int l, int r) { return sum(r) - sum(l - 1); }; long long count_swaps(vector<int> a) { n = a.size(); int i, j; for(i = 0; i < n; i++) { if(a[i] > 0) l[a[i]].push(i + 1); else r[-a[i]].push(i + 1); } int ans = 0; for(i = 0; i < n; i++) { if(a[i] > 0) { if(l[a[i]].front() != i + 1) continue; l[a[i]].pop(); int id = r[a[i]].front(); r[a[i]].pop(); ans += (id - i - 1 - qry(i + 1, id)); //cout << i << " " << a[i] << " " << id - i - qry(i + 1, id) << endl; upd(id, 1); } else { if(r[-a[i]].front() != i + 1) continue; r[-a[i]].pop(); int id = l[-a[i]].front(); l[-a[i]].pop(); ans += (id - i - 2 - qry(i + 1, id)); //cout << i << " " << a[i] << " " << id - i - 1 - qry(i + 1, id) << endl; upd(id, 1); } } return ans; } /* int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(0); int i,j; cin >> n; vector<int> a(2 * n); for(auto &x : a) cin >> x; cout << count_swaps(a) << endl; return 0; }*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:24:26: warning: unused variable 'j' [-Wunused-variable]
   24 |     n = a.size(); int i, j;
      |                          ^
#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...