Submission #1063571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063571		aaaaaarroz	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	1 ms	344 KiB

shoes

    #include <bits/stdc++.h>
    using namespace std;
    template<class T, T m_(T, T)> struct IterativeSegmentTree{
      int n; vector<T> ST;
      IterativeSegmentTree(){}
      IterativeSegmentTree(vector<T> &a){
        n = a.size(); ST.resize(n << 1);
        for (int i=n;i<(n<<1);i++)ST[i]=a[i-n];
        for (int i=n-1;i>0;i--)ST[i]=m_(ST[i<<1],ST[i<<1|1]);
      }
      void update(int pos, T val){ // replace with val
        ST[pos += n] += val;
        for (pos >>= 1; pos > 0; pos >>= 1)
          ST[pos] = m_(ST[pos<<1], ST[pos<<1|1]);
      }
      T query(int l, int r){ // [l, r]
        T ansL, ansR; bool hasL = 0, hasR = 0;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
          if (l & 1) 
            ansL=(hasL?m_(ansL,ST[l++]):ST[l++]),hasL=1;
          if (r & 1) 
            ansR=(hasR?m_(ST[--r],ansR):ST[--r]),hasR=1;
        }
        if (!hasL) return ansR; if (!hasR) return ansL;
        return m_(ansL, ansR);
      }
    };
    int merge(int a, int b){
    	return a+b;
    }
    long long count_swaps(vector<int> s)
    {
       vector< pair<int,int> > parejas;
       map<int,queue<int> > last;
       for (int i = int(s.size())-1; i >= 0; --i)
       {
          int x = s[i];
          if (!last[-x].empty())
          {
             parejas.emplace_back(i, last[-x].front());
             last[-x].pop();
          }
          else
             last[x].push(i);
       }
       reverse(parejas.begin(), parejas.end());
       long long ret = 0;
       vector<int>mudo(s.size(),0);
       IterativeSegmentTree<int,merge>st(mudo);
       for (auto p : parejas)
       {
          int l, r;
          tie(l, r) = p;
          int steps = r - l - 1 - st.query(l+1, r-1);
          if (s[l] > 0) {
             ++steps;
          }
          ret += steps;
          st.update(r, 1);
       }
        return ret;
    }

Compilation message (stderr)

shoes.cpp: In member function 'T IterativeSegmentTree<T, m_>::query(int, int)':
shoes.cpp:24:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   24 |         if (!hasL) return ansR; if (!hasR) return ansL;
      |         ^~
shoes.cpp:24:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   24 |         if (!hasL) return ansR; if (!hasR) return ansL;
      |                                 ^~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:54:52: warning: 'ansR' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |           int steps = r - l - 1 - st.query(l+1, r-1);
      |                                                    ^

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15