Submission #392028

#	Time	Username	Problem	Language	Result	Execution time	Memory
392028		AugustinasJucas	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	303 ms	22456 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
struct node{
    int val, l, r, plus;
};
struct seg_tree{
    
    vector<node> tree;
    int currInd = 0;
    int n;
    
    void build(int v){
        if(v >= n){
            tree[v].l = tree[v].r = currInd++;
            tree[v].val = tree[v].plus = 0;
        }else{
            build(v*2);
            build(v*2+1);
            tree[v].l = tree[v*2].l;
            tree[v].r = tree[v*2+1].r;
        }
    }
    void apply(int v){
        tree[v].val += tree[v].plus * (tree[v].r - tree[v].l + 1);
        if(v < n) tree[v*2].plus += tree[v].plus;
        if(v < n) tree[v*2+1].plus += tree[v].plus;
        tree[v].plus = 0;
    }
    void add(int v, int l, int r, int x){
        apply(v);
        if(tree[v].l >= l && tree[v].r <= r){ /// sitas pilnai telpa intervale
            tree[v].plus += x;
        }else if(tree[v].l > r || tree[v].r < l){
            
        }else {
            add(v*2, l, r, x);
            add(v*2+1, l, r, x);
            tree[v].val = tree[v*2].val + tree[v*2+1].val;
        }
        apply(v);
    }
    int find(int v, int l, int r){
        apply(v);
        if(tree[v].l >= l && tree[v].r <= r){ /// sitas pilnai telpa intervale
            return tree[v].val;
        }else if(tree[v].l > r || tree[v].r < l){
            return 0;
        }else {
            return find(v*2, l, r) + find(v*2+1, l, r);
        }
    }
    seg_tree(int dydis){
        tree.resize(dydis*2+10);
        n = dydis;
        build(1);
    }
};
const int dydis = 1e5  + 1;
vector<int> kurL[dydis];
vector<int> kurR[dydis];
seg_tree medis(dydis * 2 + 1);
long long count_swaps(vector<int> s) {
    for(int i = 0; i < s.size(); i++) medis.add(1, i, i, i);
    for(int i = 0; i < s.size(); i++){
        if(s[i] > 0) kurR[s[i]].push_back(i);
        else kurL[-s[i]].push_back(i);
    }
    vector<pair<pair<int, int>, int> > poros;
    int n = s.size()/2;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < kurL[i].size(); j++){
            if(kurL[i][j] < kurR[i][j]){
                poros.push_back({{kurL[i][j], kurR[i][j]}, 0});
            }else{
                poros.push_back({{kurR[i][j], kurL[i][j]}, 1});
            }
        }
    }
    sort(poros.begin(), poros.end());
    reverse(poros.begin(), poros.end());

    int realIndex[s.size() + 1];
    for(int i = 0; i < s.size(); i++) realIndex[i] = i;
    long long ans = 0;
    for(auto x : poros){
        int i1 = medis.find(1, x.first.first, x.first.first);
        int i2 = medis.find(1, x.first.second, x.first.second) - 1 + x.second;
//        cout << "i1 = " << i1 << ", i2 = " << i2 << endl;
        ans += i2-i1;
        medis.add(1, x.first.first+1, x.first.second-1+x.second, -1);
    }

	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0; i < s.size(); i++) medis.add(1, i, i, i);
      |                    ~~^~~~~~~~~~
shoes.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i = 0; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
shoes.cpp:71:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int j = 0; j < kurL[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~~~~
shoes.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int i = 0; i < s.size(); i++) realIndex[i] = i;
      |                    ~~^~~~~~~~~~
shoes.cpp:82:9: warning: variable 'realIndex' set but not used [-Wunused-but-set-variable]
   82 |     int realIndex[s.size() + 1];
      |         ^~~~~~~~~

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