oj.uz

Submission #642098

# Submission time Handle Problem Language Result Execution time Memory
642098 2022-09-18T12:59:36 Z messiuuuuu OGLEDALA (COI15_ogledala) C++17
41 / 100
 4000 ms 201296 KB 
///
#include<bits/stdc++.h>
#define task "C"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
using namespace std;
const int MAXN = 3e5 + 5;
const ll INF = 1e18 + 5;

struct TLine
{
    ll le, sl;
    int id;
};
vector<TLine> all;

map<ll, ll> mp;

void Proc(ll l, ll r)
{
    mp.clear();
    if (l > r)
        return;
    deque<ll> Q;
    mp[r - l + 1] = 1;
    Q.pb(r - l + 1);
    while (!Q.empty())
    {
        ll u = Q.front();
        ll d = mp[u];
        Q.pop_front();
        if (u / 2 > 1 && !mp.count(u / 2))
            Q.pb(u / 2);
        mp[u / 2] += d;
        u--;
        if (u / 2 > 1 && !mp.count(u / 2))
            Q.pb(u / 2);
        mp[u / 2] += d;
    }
}

int n, q;
ll m;
pair<ll, ll> b[MAXN];
ll a[MAXN];

void Input()
{
    cin >> m >> n >> q;
    ll last = 0;
    for (int i = 1; i <= n + 1; i++)
    {
        if (i <= n)
            cin >> a[i];
        else
            a[i] = m + 1;
        b[i] = {last + 1, a[i] - 1};
        Proc(last + 1, a[i] - 1);

        for (auto& p : mp)
        {
            //cerr << p.fi << ' ' << p.se << ' ' << i << '\n';
            all.pb({p.fi, p.se, i});
        }

        last = a[i];
    }
}

ll sum[MAXN * 100];
ll res;

void Dnc(ll l, ll r, ll le, ll sl)
{
    if (r - l + 1 == le)
    {
        res = (l + r) >> 1;
        return;
    }
    ll mid = (l + r) >> 1;
    Proc(l, mid - 1);

    if (sl <= mp[le])
    {
        Dnc(l, mid - 1, le, sl);
    } else
    {
        sl -= mp[le];
        Dnc(mid + 1, r, le, sl);
    }
}

void Solve()
{
    sort(all.begin(), all.end(), [](const auto& i, const auto& j)
         {
             return i.le > j.le || i.le == j.le && i.id < j.id;
         });

    //cerr << all[0].sl << '\n';

    sum[0] = all[0].sl;
    for (int i = 1; i < all.size(); i++)
        sum[i] = sum[i - 1] + all[i].sl;

    while (q-- > 0)
    {
        ll c;
        cin >> c;
        if (c <= n)
        {
            cout << a[c] << '\n';
            continue;
        }
        c -= n;
        int p = lower_bound(sum, sum + all.size(), c) - sum;
        //cerr << p << '\n';

        c -= (p == 0 ? 0 : sum[p - 1]);
        //cerr << c << '\n';
        res = -1;
        Dnc(b[all[p].id].fi, b[all[p].id].se, all[p].le, c);
        cout << res << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message

ogledala.cpp: In function 'void Solve()':
ogledala.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TLine>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 1; i < all.size(); i++)
      |                     ~~^~~~~~~~~~~~
ogledala.cpp: In instantiation of 'Solve()::<lambda(const auto:23&, const auto:24&)> [with auto:23 = TLine; auto:24 = TLine]':
/usr/include/c++/10/bits/predefined_ops.h:156:30:   required from 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Iterator2 = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Compare = Solve()::<lambda(const auto:23&, const auto:24&)>]'
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<Solve()::<lambda(const auto:23&, const auto:24&)> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<TLine*, std::vector<TLine> >; _Compare = Solve()::<lambda(const auto:23&, const auto:24&)>]'
ogledala.cpp:101:11:   required from here
ogledala.cpp:100:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  100 |              return i.le > j.le || i.le == j.le && i.id < j.id;
      |                                    ~~~~~~~~~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:136:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 61 ms 2648 KB Output is correct
4 Correct 46 ms 2896 KB Output is correct
5 Correct 81 ms 9720 KB Output is correct
6 Correct 73 ms 10844 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 672 KB Output is correct
2 Correct 146 ms 708 KB Output is correct
3 Correct 1605 ms 200792 KB Output is correct
4 Correct 1391 ms 200552 KB Output is correct
5 Correct 1764 ms 200484 KB Output is correct
6 Correct 1622 ms 200408 KB Output is correct

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 2686 ms 101452 KB Output is correct
2 Correct 2591 ms 104004 KB Output is correct
3 Execution timed out 4090 ms 201296 KB Time limit exceeded
4 Halted 0 ms 0 KB -