oj.uz

Submission #144338

# Submission time Handle Problem Language Result Execution time Memory
144338 2019-08-16T16:50:30 Z CodeKracker Arranging Shoes (IOI19_shoes) C++14
10 / 100
 2 ms 376 KB 
/*input

*/
/**
    Author: Kristopher Paul
    Date Created: 16-08-2019
    Contest Name:
                _/    _/   _/_/_/_/   _/   _/_/_/_/
               _/  _/     _/    _/   _/   _/
              _/_/       _/_/_/_/   _/   _/_/_/_/
             _/  _/     _/  _/     _/         _/
            _/    _/   _/    _/   _/   _/_/_/_/
**/
#include<iostream>
#include<unordered_map>
#include<vector>
#include<cmath>
#define ll long long
#define pb push_back
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define umap unordered_map
#define vi vector<int>
using namespace std;

struct segnode
{
    int lazy;
    int val;
};

segnode tree[400005];

void build(int node,int s,int e){
    if(s == e){
        tree[node].lazy = 0;
        tree[node].val = 0;
        return;
    }
    int m = (s+e)/2;
    build(node*2,s,m);
    build(node*2+1,m+1,e);
    tree[node].lazy = 0;
    tree[node].val = 0;
}

void upd(int node,int s,int e,int l,int r,int v){
    if(tree[node].lazy != 0){
        tree[node].val += (tree[node].lazy*(e-s+1));
        if(s != e){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
    if(s > r || e < l || s > e || l > r){
        return;
    }
    if(l <= s && e <= r){
        tree[node].val += (v*(e-s+1));
        if(s != e){
            tree[node*2].lazy += v;
            tree[node*2+1].lazy += v;
        }
        return;
    }
    int m = (s+e)/2;
    upd(node*2,s,m,l,r,v);
    upd(node*2+1,m+1,e,l,r,v);
    tree[node].val = tree[node*2].val + tree[node*2+1].val;
}

int query(int node,int s,int e,int pos){
    if(tree[node].lazy != 0){
        tree[node].val += (tree[node].lazy*(e-s+1));
        if(s != e){
            tree[node*2].lazy += tree[node].lazy;
            tree[node*2+1].lazy += tree[node].lazy;
        }
        tree[node].lazy = 0;
    }
    if(s > pos || e < pos || s > e){
        return 0;
    }
    if(s == pos && pos == e){
        return tree[node].val;
    }
    int m = (s+e)/2;
    int a = query(node*2,s,m,pos);
    int b = query(node*2+1,m+1,e,pos);
    tree[node].val = tree[node*2].val + tree[node*2+1].val;
    return max(a,b);
}

ll count_swaps(vector<int> arr){
    int n = arr.size();
    build(1,1,n);
    umap<int,vi> op;
    bool done[n+1] = {};
    FORD(i,n-1,0){
        op[arr[i]].pb(i+1);
    }
    ll ans = 0;
    FOR(i,0,n){
        if(done[i+1]){
            continue;
        }
        if(arr[i] < 0){
            vi::iterator k = op[abs(arr[i])].end();
            k--;
            int pos = *k;
            int rpos = query(1,1,n,pos) + pos;
            done[pos] = true;
            int lpos = i+1;
            ans += rpos-lpos-1;
            upd(1,1,n,lpos+1,rpos-1,1);
            upd(1,1,n,rpos,rpos,rpos-lpos-1);
            op[abs(arr[i])].pop_back();
            op[arr[i]].pop_back();
        }else if(arr[i] > 0){
            vi::iterator k = op[-arr[i]].end();
            k--;
            int pos = *k;
            done[pos] = true;
            int rpos = i+1;
            int lpos = query(1,1,n,pos) + pos;
            ans += lpos-rpos;
            upd(1,1,n,rpos,lpos-1,1);
            upd(1,1,n,lpos,lpos,lpos-rpos);
            op[-arr[i]].pop_back();
            op[arr[i]].pop_back();
        }
    }
    return ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Incorrect 2 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -