Submission #613939

#	Time	Username	Problem	Language	Result	Execution time	Memory
613939		Mr_Husanboy	Ancient Books (IOI17_books)	C++14	50 / 100	168 ms	16964 KiB

books

#include "books.h"
#include<bits/stdc++.h>

using namespace std;
#define all(a) (a).begin(), (a).end()
#define vi vector<int>
#define ff first
#define ss second
#define ll long long


struct Fenwick{
    vector<int> t;
    void init(int n){
        t.resize(n);
    }
    void inc(int i, int d = 1){
        for(; i<t.size(); i|=i+1) t[i] += d;
    }

    int get(int i){
        int res = 0;
        for(; i>=0; i = (i&(i+1))-1) res += t[i];
        return res;
    }

    int get(int l, int r){
        return get(r) - get(l-1);
    }
};

long long minimum_walk(vector<int> p, int s) {
    int n = p.size();
    ll tot = 0;
    Fenwick tr;
    tr.init(n);
    for(int i=0; i<n; i++){
        tot += abs(i - p[i]);
        int mn = min(i, p[i]);
        int mx = max(i, p[i]);
        tr.inc(mn,1); tr.inc(mx,-1);
    }
    int r = n-1;
    while(r >=0 && tr.get(r)==0) r--;
    //cout << r << endl;
 //   cout << "done" << endl;
    ll cnt = 0;
    for(int i = 0; i <=r; i ++){
        cnt += tr.get(i)==0;
    }
    return tot + cnt*2;
}

Compilation message (stderr)

books.cpp: In member function 'void Fenwick::inc(int, int)':
books.cpp:18:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(; i<t.size(); i|=i+1) t[i] += d;
      |               ~^~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 28 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30