oj.uz

Submission #937315

# Submission time Handle Problem Language Result Execution time Memory
937315 2024-03-03T20:13:07 Z snpmrnhlol Ancient Books (IOI17_books) C++17
0 / 100
 0 ms 444 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;
ll dp[N];
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);
            //cout<<"cycle:"<<i<<' ';
            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);
            }
            //cout<<a<<' '<<b<<'\n';
            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 Incorrect 0 ms 444 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
3 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 Incorrect 0 ms 444 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
3 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 Incorrect 0 ms 444 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
3 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: '4734'
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 Incorrect 0 ms 444 KB 3rd lines differ - on the 1st token, expected: '6', found: '8'
3 Halted 0 ms 0 KB -