Submission #775789

#	Time	Username	Problem	Language	Result	Execution time	Memory
775789		Sandarach151	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	165 ms	141316 KiB

shoes

#include<bits/stdc++.h>
using namespace std;

class segmentTree{
    private:
        int sze;
        vector<int> vect;
        void privUpdate(int pos, int val, int nodepos, int nodeleft, int noderight){
            if(nodeleft==noderight){
                vect[nodepos]=val;
            }
            else{
                int nodemid = (nodeleft+noderight)/2;
                if(pos<=nodemid){
                    privUpdate(pos, val, 2*nodepos+1, nodeleft, nodemid);
                }
                else{
                    privUpdate(pos, val, 2*nodepos+2, nodemid+1, noderight);
                }
                vect[nodepos]=vect[2*nodepos+1]+vect[2*nodepos+2];
            }
        }
        int privGetSum(int queryleft, int queryright, int nodepos, int nodeleft, int noderight){
            if(queryleft>noderight || queryright<nodeleft){
                return 0;
            }
            else if(queryleft<=nodeleft && queryright>=noderight){
                return vect[nodepos];
            }
            else{
                int nodemid = (nodeleft+noderight)/2;
                return privGetSum(queryleft, queryright, 2*nodepos+1, nodeleft, nodemid)+privGetSum(queryleft, queryright, 2*nodepos+2, nodemid+1, noderight);
            }
        }
    public:
        segmentTree(int n): sze(n){
            vect.resize(4*sze, 0);
        }
        void update(int pos, int val){
            privUpdate(pos, val, 0, 0, sze-1);
        }
        int getSum(int left, int right){
            return privGetSum(left, right, 0, 0, sze-1);
        }
};


long long count_swaps(std::vector<int> s) {
    int n = s.size()/2;
	queue<int> negative[n+1];
    queue<int> positive[n+1];
    segmentTree stree(2*n);
    long long ans = 0;
    for(int i=0; i<2*n; i++){
        if(s[i]<0){
            if(!positive[-1*s[i]].empty()){
                stree.update(i, -1);
                stree.update(positive[-1*s[i]].front(), 1);
                ans+= i-positive[-1*s[i]].front()+stree.getSum(positive[-1*s[i]].front(), i);
                positive[-1*s[i]].pop();
            }
            else{
                negative[-1*s[i]].push(i);
            }
        }
        else{
            if(!negative[s[i]].empty()){
                stree.update(i, -1);
                stree.update(negative[s[i]].front(), 1);
                ans+= i-negative[s[i]].front()-1+stree.getSum(negative[s[i]].front(), i);
                negative[s[i]].pop();
            }
            else{
                positive[s[i]].push(i);
            }
        }
    }
    return ans;
}

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