Submission #893544

#	Time	Username	Problem	Language	Result	Execution time	Memory
893544		UmairAhmadMirza	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	474 ms	150736 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
int const N=2e5+5;
map<int,stack<int>> ind;
int n;
long long ans=0;
bool rem[N];
template<class TP> class SegmentTree{
    private://cannot be access outside
        //we can set constant here
        int const DEFAULT = 0;
        int const INF = 1e9;
        //global varibles
        vector<int> segtree;
        int sz;
    public:
        //constructor and it should be 4 * n in top_down segtree
        SegmentTree(int sz) : sz(sz), segtree(sz * 4, DEFAULT){};
        
        //Now here all function we want your data to have
        void recalculate(int node) {
            segtree[node] = segtree[2 * node+1] + segtree[2 * node + 2];
        }
        void update(int node, int left, int right, int ind, int val) {
            if (left == right) //we are in the indth leaf
                segtree[node] = val;
            else {
                int middle = (left + right) / 2;
                if (ind <= middle)//we need to update the left son
                    update(2 * node + 1, left, middle, ind, val);
                else
                    update(2 * node + 2, middle + 1, right, ind, val);
                //after updating said son, recalculate the current segment
                recalculate(node);
            }
        }
        int query(int node, int left, int right, int l, int r) {
            if (l <= left && right <= r) {
                //the segment of "node" is completely included in the query
                return segtree[node];
            }
            else {
                int answer = 0;
                int middle = (left + right) / 2;
                if (l <= middle) {
                    //the query segment and the left son segment have at least one element in common
                    answer += query(2 * node + 1, left, middle, l, r);
                }
                if (r > middle) {
                    //the query segment and the right son segment have at least one element in common
                    answer += query(2 * node + 2, middle + 1, right, l, r);
                }
                return answer;
            }
        }

};
long long count_swaps(vector<int> v){
	n=v.size();
	n/=2;
	for (int i = (2*n)-1; i>=0; --i)
		ind[v[i]].push(i);
	SegmentTree<int> tree(2*n);
	for (int i = 0; i < 2*n; ++i)
	{
		if(rem[i])
			continue;
		if(v[i]>0)
			ans++;
		ind[v[i]].pop();
		rem[i]=1;
		int op=v[i]*(-1);
		int index=ind[op].top();
		ind[op].pop();
		rem[index]=1;
		int swp=(index-i)-1;
		swp-=tree.query(0,1,2*n,i+1,index);
		ans+=swp;
		tree.update(0,1,2*n,index+1,1);
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In instantiation of 'SegmentTree<TP>::SegmentTree(int) [with TP = int]':
shoes.cpp:63:27:   required from here
shoes.cpp:15:13: warning: 'SegmentTree<int>::sz' will be initialized after [-Wreorder]
   15 |         int sz;
      |             ^~
shoes.cpp:14:21: warning:   'std::vector<int> SegmentTree<int>::segtree' [-Wreorder]
   14 |         vector<int> segtree;
      |                     ^~~~~~~
shoes.cpp:18:9: warning:   when initialized here [-Wreorder]
   18 |         SegmentTree(int sz) : sz(sz), segtree(sz * 4, DEFAULT){};
      |         ^~~~~~~~~~~

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