454B - Little Pony and Sort by Shift - CodeForces Solution

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <math.h>

using namespace std;

class Node
{
public:
    int64_t diff;
    int c = 0;
    int len = 0;
    int64_t ans = 0;
    Node *left = nullptr;
    Node *right = nullptr;
};

inline int64_t getRes(int64_t len)
{
    return (len) * (len);
}

inline void calc(Node *node)
{
   int add = (node->len)/(node->c+1);
   int re =(node->len)%(node->c+1);
   node->ans = re * getRes(add+1) + (node->c+1-re) * getRes(add); //+ node->c;

   //cout << "len=" << node->len << ", ans=" << node->ans << "\n";
   if (node->ans == node->len)
   {
       node->diff = 0;
       return;
   }

   int neadd = (node->len)/(node->c+2);
   int nere = (node->len)%(node->c+2);
   int64_t neans = nere * getRes(neadd+1) + (node->c+2-nere) * getRes(neadd); //+ node->c + 1;
   node->diff = node->ans - neans;
}

inline int getPos(Node *cur, int cle, int cri)
{
    if (cle == cri)
    {
        return cle;
    }

    int c = (cle+cri)/2;

    if (cur->left != nullptr && cur->right != nullptr)
    {
        if (cur->left->diff > cur->right->diff)
        {
            return getPos(cur->left, cle, c);
        }
        else
        {
            return getPos(cur->right, c+1, cri);
        }
    }

    if (cur->left != nullptr)
    {
        return getPos(cur->left, cle, c);
    }

    return getPos(cur->right, c+1, cri);
}

inline int64_t getAns(Node *cur, int le, int ri, int cle, int cri)
{
    if (le > ri || cur == nullptr)
    {
        return 0;
    }

    if (cle == le && cri == ri)
    {
        return cur->ans;
    }

    int c = (cle+cri)/2;

    return getAns(cur->left, le, min(c, ri), cle, c) +
               getAns(cur->right, max(c+1, le), ri, c+1, cri);
}

inline void setLen(Node **cur, int pos, int64_t res, int cle, int cri)
{
    //cout << "pos=" << pos << ", cle=" << cle << ", cri=" << cri << "\n";

    if (*cur == nullptr)
    {
        *cur = new Node();
    }

    if (cle == cri && pos == cle)
    {
        (*cur)->len = res;
        (*cur)->c = 0;
        calc(*cur);
        return;
    }

    int c = (cle+cri)/2;

    if (pos > c)
    {
        setLen(&((*cur)->right), pos, res, c+1, cri);
    }
    else
    {
        setLen(&((*cur)->left), pos, res, cle, c);
    }

    //(*cur)->ans = max(res, (*cur)->ans);
    (*cur)->diff = 0;
    (*cur)->ans = 0;
    if (((*cur)->left) != nullptr)
    {
        (*cur)->diff = max((*cur)->diff,((*cur)->left)->diff);
        (*cur)->ans += ((*cur)->left)->ans;
    }

    if (((*cur)->right) != nullptr)
    {
        (*cur)->diff = max((*cur)->diff, ((*cur)->right)->diff);
        (*cur)->ans += ((*cur)->right)->ans;
    }

    //cout << "pos=" << pos << ", cle=" << cle << ", cri=" << cri << ", ans=" << (*cur)->ans << "\n";
}

inline void incC(Node **cur, int pos, int cle, int cri)
{
    //cout << "pos=" << pos << ", cle=" << cle << ", cri=" << cri << "\n";
    if (*cur == nullptr)
    {
        *cur = new Node();
    }

    if (cle == cri && pos == cle)
    {
        (*cur)->c++;
        calc(*cur);
        return;
    }

    int c = (cle+cri)/2;

    if (pos > c)
    {
        incC(&((*cur)->right), pos, c+1, cri);
    }
    else
    {
        incC(&((*cur)->left), pos, cle, c);
    }

    //(*cur)->ans = max(res, (*cur)->ans);
    (*cur)->diff = 0;
    (*cur)->ans = 0;
    if (((*cur)->left) != nullptr)
    {
        (*cur)->diff = max((*cur)->diff,((*cur)->left)->diff);
        (*cur)->ans += ((*cur)->left)->ans;
    }

    if (((*cur)->right) != nullptr)
    {
        (*cur)->diff = max((*cur)->diff, ((*cur)->right)->diff);
        (*cur)->ans += ((*cur)->right)->ans;
    }
}

void clearTree(Node *cur, int cle, int cri)
{
    if (cle == cri)
    {
        delete cur;
    }

    int c = (cle+cri)/2;

    if (cur->left != nullptr)
    {
        clearTree(cur->left, cle, c);
    }

    if (cur->right != nullptr)
    {
        clearTree(cur->right, c+1, cri);
    }
}

int64_t mod = 1000000007;

int a[100000];

void solve()
{
    int n;
    cin >> n;

    int mix = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
        if (a[i] < a[mix])
        {
            mix = i;
        }
    }

    if (mix == 0)
    {
        int pos = n-1;
        int res = mix;
        while (pos >= mix && a[pos] == a[mix]) {res = pos--;}
        mix = res;
    }

    int prev = mix;
    for (int i = (mix+1)%n; i != mix; i = (i+1)%n)
    {
        if (a[i] < a[prev])
        {
            cout << "-1\n";
            return;
        }

        prev = i;
    }

    cout << (n-mix)%n << "\n";
}

int main()
{
    /*char del = ',';
    char star = '.';

    printf("del=0x%2X, star=0x%2X\n", del, star);
    return 0;*/
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    //iostream::sync_with_stdio(0);


    int t = 1;
    //cin >> t;
    //getchar();

    for (int i = 0; i < t; ++i)
    {
        solve();
    }

    return 0;
}