Submission #1049344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049344		MrPavlito	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	116 ms	34904 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define sc second
#define endl "\n"
#define pii pair<int,int>

using namespace std;

const int MAXN = 2e5+5;
const int offse = 1e5;
const int mod7 = 1e9+7;
const long long inf = 1e18;

vector<long long> seg(MAXN<<2);
vector<long long> lazy(MAXN<<2);
bool visited[MAXN];
vector<set<int>> closest(MAXN);

void push(int nod, int tl, int tr)
{
    if(!lazy[nod])return;
    if(tl != tr)
    {
        lazy[nod<<1] += lazy[nod];
        lazy[nod<<1|1] += lazy[nod];
    }
    seg[nod] += (tr-tl+1)*lazy[nod];
    lazy[nod] = 0;
}

void update(int nod, int tl, int tr, int l, int r)
{
    push(nod, tl, tr);
    if(tl>r || tl> tr || tr<l)return;
    if(tl>=l && tr<=r)
    {
        lazy[nod]++;
        //push(nod,tl,tr);
        return;
    }
    int mid = tl+tr>>1;
    update(nod<<1, tl, mid,l,r);
    update(nod<<1|1, mid+1, tr,l,r);
    seg[nod] = seg[nod<<1] + seg[nod<<1|1];
}

long long query(int nod,int tl, int tr, int l, int r)
{
    push(nod, tl ,tr);
    if(tl>r || tl> tr || tr<l)return 0;
    if(tl>=l && tr<=r)return seg[nod];
    int mid = tl+tr>>1;
    return query(nod<<1, tl, mid,l,r) + query(nod<<1|1, mid+1, tr,l,r);
}

long long count_swaps(std::vector<int> s) {
    int n = s.size();
    long long rez = 0;
    for(int i=0;i < n; i++)closest[s[i]+offse].insert(i);
    for(int i=0; i<n; i++)
    {
        if(visited[i])continue;
        if(s[i] < 0)
        {
            int trazi = -s[i] + offse;
            int poz = *closest[trazi].begin();
            visited[poz] = 1;
            closest[trazi].erase(closest[trazi].begin());
            closest[s[i]+offse].erase(closest[s[i]+offse].begin());
            int pravapoz = i+query(1,1,n,i,i);
            int novapoz = poz+query(1,1,n,poz,poz);
            update(1,1,n, i, poz);
            rez+= novapoz - pravapoz - 1;
        }
        else
        {
            int trazi = -s[i] + offse;
            int poz = *closest[trazi].begin();
            visited[poz] = 1;
            closest[trazi].erase(closest[trazi].begin());
            closest[s[i]+offse].erase(closest[s[i]+offse].begin());
            int pravapoz = i+query(1,1,n,i,i);
            int novapoz = poz+query(1,1,n,poz,poz);
            update(1,1,n, i, poz);
            rez+= novapoz - pravapoz;
        }
    }
    return rez;


}
/*
2
2 1 -1 -2
*/

/*
3
-2 2 2 -2 -2 2
*/

Compilation message (stderr)

shoes.cpp: In function 'void update(int, int, int, int, int)':
shoes.cpp:46:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = tl+tr>>1;
      |               ~~^~~
shoes.cpp: In function 'long long int query(int, int, int, int, int)':
shoes.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = tl+tr>>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