Submission #937315

#	Time	Username	Problem	Language	Result	Execution time	Memory
937315		snpmrnhlol	Ancient Books (IOI17_books)	C++17	0 / 100	0 ms	444 KiB

books

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30