oj.uz

Submission #294221

# Submission time Handle Problem Language Result Execution time Memory
294221 2020-09-08T17:22:22 Z Kastanda Ancient Books (IOI17_books) C++11
0 / 100
 1 ms 512 KB 
// M
#include<bits/stdc++.h>
#include "books.h"
using namespace std;
typedef long long ll;
const int N = 1000006, LG = 20;
int n, st, A[N], mnq[LG][N], mxq[LG][N], Log[N];
map < pair < int , int > , pair < int , int > > MP;
inline int GetMin(int l, int r)
{
        int lg = Log[r - l];
        return min(mnq[lg][l], mnq[lg][r - (1 << lg)]);
}
inline int GetMax(int l, int r)
{
        int lg = Log[r - l];
        return max(mxq[lg][l], mxq[lg][r - (1 << lg)]);
}
inline pair < int , int > Extend(pair < int , int > nw)
{
        while (true)
        {
                pair < int , int > tb;
                tb.first = min(nw.first, GetMin(nw.first, nw.second + 1));
                tb.second = max(nw.second, GetMax(nw.first, nw.second + 1));
                if (tb == nw)
                        break;
                nw = tb;
        }
        return nw;
}

long long minimum_walk(vector < int > _A, int _st)
{
        n = (int)_A.size();
        st = _st + 1;
        for (int i = 1; i <= n; i ++)
                A[i] = _A[i - 1] + 1;

        for (int i = 2; i <= n; i ++)
                Log[i] = Log[i >> 1] + 1;
        for (int i = 1; i <= n; i ++)
                mnq[0][i] = mxq[0][i] = A[i];
        for (int j = 1; j < LG; j ++)
                for (int i = 1; i + (1 << j) <= n + 1; i ++)
                {
                        mnq[j][i] = min(mnq[j - 1][i], mnq[j - 1][i + (1 << (j - 1))]);
                        mxq[j][i] = max(mxq[j - 1][i], mxq[j - 1][i + (1 << (j - 1))]);
                }

        ll SM = 0;
        for (int i = 1; i <= n; i ++)
                SM += abs(A[i] - i);

        int Mn = 1, Mx = n;
        while (Mn < st && A[Mn] == Mn)
                Mn ++;
        while (Mx > st && A[Mx] == Mx)
                Mx --;

        pair < int , int > nw = {st, st};
        nw = Extend(nw);

        while (nw != make_pair(Mn, Mx))
        {
                int cle = 0, cri = 0;
                pair < int , int > gle = nw, gri = nw;
                while (gle.first > 1 && gle.second == nw.second)
                        cle ++, gle = Extend({gle.first - 1, gle.second});
                while (gri.second < n && gri.first == nw.first)
                        cri ++, gri = Extend({gri.first, gri.second + 1});
                if (gle == gri)
                        SM += min(cle, cri) * 2, nw = gle;
                else
                        SM += (cle + cri) * 2, nw = make_pair(Mn, Mx);
        }
        return SM;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Incorrect 1 ms 512 KB 3rd lines differ - on the 1st token, expected: '2094', found: '2108'
5 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Incorrect 1 ms 384 KB 3rd lines differ - on the 1st token, expected: '4', found: '6'
11 Halted 0 ms 0 KB -