Submission #987017

#	Time	Username	Problem	Language	Result	Execution time	Memory
987017		aaaaaarroz	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	242 ms	278204 KiB

shoes

    #include "shoes.h"
    #include <bits/stdc++.h>
     
    using namespace std;
    const int N = 400010;
    queue <int> q[N];
    int res[N];
    int dp[N];
     
    struct Segtree{
    	int tree[4*N];
    	int join(int a, int b){
    		return a+b;
    	}
    	void build(int node, int l,int r){
    		if(l == r){
    			tree[node] = 0;
    			return;
    		}
    		int mid = (l+r)/2;
    		build(2*node, l, mid);
    		build(2*node+1, mid+1, r);
    		tree[node] = 0;
    		return;
    	}
    	void update(int node, int l, int r, int pos){
    		if(l == r){
    			tree[node] = 1;
    			return;
    		}
    		int mid = (l+r)/2;
    		if(l <= pos and pos <= mid) update(2*node, l, mid, pos);
    		else update(2*node+1, mid+1, r, pos);
    		tree[node] = join(tree[2*node], tree[2*node+1]);
    	}
    	int query(int node, int l, int r, int tl, int tr){
    		if(l <= tl and tr <= r) return tree[node];
    		if(l > tr or tl > r) return 0;
    		int mid = (tl+tr)/2;
    		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
    	}
    } seg;
     
    long long count_swaps(std::vector<int> v) {
    	int n = v.size();
    	int num = n;
    	for(int i = v.size()-1;i >= 0;i--){
    		if(q[v[i]+n].empty()){
    			if(v[i] > 0){
    				res[i+1] = num;
    				q[n-v[i]].push(num-1);
    			}
    			else{
    				res[i+1] = num-1;
    				q[n-v[i]].push(num);
    			}
    			num -= 2;
    		}
    		else{
    			res[i+1] = q[v[i]+n].front();
    			q[v[i]+n].pop();
    		}
    	}
    	long long resp = 0;
    	for(int i = 1;i <= n;i++){
    		// cout << res[i] << ' ';
    		resp += seg.query(1, res[i], n, 1, n);
    		seg.update(1, 1, n, res[i]);
    	}
    	return resp;
    }

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