Submission #24181

#	Time	Username	Problem	Language	Result	Execution time	Memory
24181		chpipis	OGLEDALA (COI15_ogledala)	C++11	41 / 100	4000 ms	318832 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, pos;
    bool operator <(const state &rhs) const {
        if (len == rhs.len)
            return pos < rhs.pos;
        return len > rhs.len;
    }
};

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

void solve(ll x, ll pos) {
    map<ll, ll> val;
    queue<ll> Q;

    Q.push(x);
    val[x] = 1;
    while (!Q.empty()) {
        ll u = Q.front();
        Q.pop();

        vector<ll> gr = {(u - 1) / 2, u / 2};
        for (auto v : gr) {
            if (!val.count(v)) {
                Q.push(v);
            }
            val[v] += val[u];
        }
    }

    for (auto it : val)
        if (it.fi != 0)
            seg.pb((state){it.fi, it.se, pos});
}

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

ll freq(ll len, ll want) {
    if (len < want) return 0;
    if (len == want) return 1;
    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++;
            printf("%lld\n", a[seg[k].pos] + getans(a[seg[k].pos + 1] - a[seg[k].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:127: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:129:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
                             ^
ogledala.cpp:151: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: 0 / 59