oj.uz

Submission #937316

# Submission time Handle Problem Language Result Execution time Memory
937316 2024-03-03T20:17:16 Z snpmrnhlol Ancient Books (IOI17_books) C++17
0 / 100
 0 ms 348 KB 
#include "books.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e6;
const ll inf = 1e18;
class fenwick{
private:
    vector <ll> fen;
    ll n;
public:
    void init(ll sz,ll x = 0){
        fen.resize(sz);
        n = sz;
        for(ll i = 0;i < n;i++)fen[i] = x;
    };
    void add(ll pos,ll nr = 1){
        for(ll i = pos;i < n;i|=(i + 1)){
            fen[i] = max(fen[i],nr);
        }
    };
    ll get(ll pos,ll rinit = 0){
        ll r = rinit;
        for(ll i = pos;i >= 0;i&=(i + 1),i--){
            r+=fen[i];
        }
        return r;
    }
};
fenwick fen;
bool vis[N];
vector <ll> points;
long long minimum_walk(std::vector<int> p, int s) {
    ll n = p.size();
    fen.init(n);
    ll ans = 0;
    for(ll i=  0;i < n;i++){
        ans+=abs(i - p[i]);
        if(!vis[i]){
            ll nr = p[i];
            while(nr != i){
                points.push_back(nr);
                nr = p[nr];
            }
            points.push_back(nr);
            if(points.size() == 1){
                points.clear();
                continue;
            }
            ll a = -1,b = inf;
            for(auto j:points){
                vis[j] = 1;
                if(j <= s)a = max(a,j);
                if(j >= s)b = min(b,j);
            }
            fen.add(a + 1,b);
            points.clear();
        }
    }
    ll mn = inf;
    for(ll i = 0;i <= s;i++){
        mn = min(mn,fen.get(i) - i);
    }
    //cout<<ans<<' '<<mn<<'\n';
    ans+=2*mn;
	return ans;
}

Subtask #1
0 / 12.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 28.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4724'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

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