oj.uz

Submission #24183

# Submission time Handle Problem Language Result Execution time Memory
24183 2017-06-01T10:20:46 Z chpipis OGLEDALA (COI15_ogledala) C++11
41 / 100
 4000 ms 297812 KB 
#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;
    }
};

void comp(ll x, 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];
        }
    }
}

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

void solve(ll x, int pos) {
    map<ll, ll> val;
    comp(x, val);

    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) {
    map<ll, ll> val;
    comp(len, val);
    return val[want];
    /*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

ogledala.cpp: In function 'int main()':
ogledala.cpp:140: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:142:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &a[i]);
                             ^
ogledala.cpp:164:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &x);
                          ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2812 KB Output is correct
2 Correct 0 ms 2812 KB Output is correct
3 Correct 236 ms 5200 KB Output is correct
4 Correct 149 ms 5200 KB Output is correct
5 Correct 156 ms 12112 KB Output is correct
6 Correct 159 ms 12112 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 3184 KB Output is correct
2 Correct 359 ms 3184 KB Output is correct
3 Correct 2623 ms 297812 KB Output is correct
4 Correct 2313 ms 297808 KB Output is correct
5 Correct 2766 ms 297812 KB Output is correct
6 Correct 2626 ms 297812 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4000 ms 150356 KB Execution timed out
2 Halted 0 ms 0 KB -