Submission #24190

#	Time	Username	Problem	Language	Result	Execution time	Memory
24190		chpipis	OGLEDALA (COI15_ogledala)	C++11	100 / 100	2176 ms	297804 KiB

ogledala

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define fast_io_without_cstdio ios_base::sync_with_stdio(false), cin.tie(NULL)
#define all(v) (v).begin(), (v).end()

#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc getchar
#define pc putchar
#endif

#if __cplusplus <= 199711L
template<class BidirIt>
BidirIt prev(BidirIt it, typename iterator_traits<BidirIt>::difference_type n = 1) {
    advance(it, -n);
    return it;
}

template<class ForwardIt>
ForwardIt next(ForwardIt it, typename iterator_traits<ForwardIt>::difference_type n = 1) {
    advance(it, n);
    return it;
}
#endif

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef long double ldouble;

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

template<typename T>
inline T sq(T a) { return a * a; }

//#ifdef LOCAL_MACHINE
//#endif

const int MAXN = 1e5 + 5;

struct state {
    ll len, cnt;
    int pos;
    inline bool operator <(const state &rhs) const {
        if (len == rhs.len)
            return pos < rhs.pos;
        return len > rhs.len;
    }
};

vector<pair<ll, ll> > vec;

void comp(ll x) {
    vec.clear();
    if (x == 0) return;

    vec.pb({x + 1, 0});
    vec.pb({x, 1});

    for (int i = 0; i < (int)vec.size(); i += 2) {
        ll len_fi = vec[i].fi / 2, cnt_fi = vec[i].se;
        ll len_se = (vec[i + 1].fi - 1) / 2, cnt_se = vec[i + 1].se;
        if (len_fi == 0 && len_se == 0) break;

        if ((vec[i].fi - 1) / 2 == len_fi)
            cnt_fi += vec[i].se;
        else
            cnt_se += vec[i].se;

        if (vec[i + 1].fi / 2 == len_fi)
            cnt_fi += vec[i + 1].se;
        else
            cnt_se += vec[i + 1].se;

        vec.pb({len_fi, cnt_fi});
        vec.pb({len_se, cnt_se});
    }

    while (!vec.empty() && vec.back().fi == 0) vec.pop_back();
    ll one = 0;
    while (!vec.empty() && vec.back().fi == 1) {
        one += vec.back().se; vec.pop_back();
    }
    if (one > 0) vec.pb({1, one});
}

vector<state> seg;
vector<ll> pref;

void solve(ll x, int pos) {
    comp(x);

    for (auto it : vec)
        seg.pb((state){it.fi, it.se, pos});
}

//map<pair<ll, ll>, ll> memo;

ll freq(ll len, ll want) {
    comp(len);
    ll res = 0;
    for (auto it : vec)
        if (it.fi == want)
            res += it.se;
    return res;
    /*if (len < want) return 0;
    if (len == want) return 1;
    ll L = (len - 1) / 2, R = len / 2;
    if (L == R) return 2LL * freq(L, want);
    return freq(L, want) + freq(R, want);
    //if (memo.count(mp(len, want)))
      //  return memo[mp(len, want)];
    //return memo[mp(len, want)] = freq((len - 1) / 2, want) + freq(len / 2, want);
    */
}

ll getans(ll len, ll want, ll k) {
    //printf("ans for (%lld, %lld, %lld):", len, want, k);
    ll ret = 0;
    while (len > want) {
        ll L = (len - 1) / 2;
        ll R = len / 2;
        ll cur = freq(L, want);
        //printf("%lld contains %lld of type %lld\n", L, cur, want);
        if (cur >= k) {
            len = L;
        } else {
            len = R;
            k -= cur;
            ret += L + 1;
        }
    }
    ret += (want + 1) / 2;
    //printf(" %lld\n", ret);
    return ret;
}

ll a[MAXN];

int main() {
    //freopen("", "r", stdin);
    //freopen("", "w", stdout);
    ll m;
    int n, q;
    scanf("%lld %d %d", &m, &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]);
    a[0] = 0;
    a[n + 1] = m + 1;
    for (int i = 0; i <= n; i++) {
        if (a[i + 1] - a[i] - 1 > 0)
            solve(a[i + 1] - a[i] - 1, i);
    }
    sort(all(seg));
    int sz = (int)seg.size();

    //for (auto it : seg)
      //  printf("(%lld, %lld, %lld)\n", it.len, it.cnt, it.pos);

    pref.resize(sz);

    pref[0] = seg[0].cnt;
    for (int i = 1; i < sz; i++)
        pref[i] = pref[i - 1] + seg[i].cnt;

    int k = 0;
    while (q--) {
        ll x;
        scanf("%lld", &x);
        if (x <= n)
            printf("%lld\n", a[x]);
        else {
            x -= n;
            while (k < sz - 1 && pref[k] < x) k++;
            int pos = seg[k].pos;
            printf("%lld\n", a[pos] + getans( a[pos + 1] - a[pos] - 1, seg[k].len, x - (k == 0 ? 0 : pref[k - 1]) ) );
        }
    }
    return 0;
}

Compilation message (stderr)

ogledala.cpp: In function 'int main()':
ogledala.cpp:157:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld %d %d", &m, &n, &q);
                                    ^
ogledala.cpp:159:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
                             ^
ogledala.cpp:181:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &x);
                          ^

• Subtask 1: 19 / 19
• Subtask 2: 22 / 22
• Subtask 3: 59 / 59