Submission #211179

#TimeUsernameProblemLanguageResultExecution timeMemory
211179lyhArranging Shoes (IOI19_shoes)C++14
100 / 100
232 ms140408 KiB
#include "shoes.h" #include <bits/stdc++.h> using namespace std; const int maxn= 2e5 + 10; const int n= 1e5 + 1; bool vis[maxn]; queue< int > q[maxn]; long long bit[maxn]; vector< int > v; int lowbit(int a) { return a & (-a); } void modify(int a, int x) { while(a <= maxn) { bit[a]+= x; a+= lowbit(a); } } long long query(int a) { long long res= 0; while(a > 0) { res+= bit[a]; a-= lowbit(a); } return res; } long long count_swaps(std::vector< int > s) { long long tot= 0; for(int i= 0; i < s.size(); i++) { q[s[i] + n].push(i + 1); modify(i + 1, 1); } for(int i= 0; i < s.size(); i++) { if(vis[i + 1]) continue; int cnt= s[i]; int y= q[-s[i] + n].front(); q[s[i] + n].pop(); q[-s[i] + n].pop(); tot+= query(y - 1) - query(i + 1); modify(i + 1, -1); modify(y, -1); vis[i + 1]= 1; vis[y]= 1; if(cnt > 0) tot++; } return tot; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:30:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i= 0; i < s.size(); i++) {
                ~~^~~~~~~~~~
shoes.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i= 0; i < s.size(); i++) {
                ~~^~~~~~~~~~
#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...