oj.uz

답안 #642119

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
642119 2022-09-18T14:36:06 Z messiuuuuu OGLEDALA (COI15_ogledala) C++14
41 / 100
 4000 ms 200188 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 = 1e5 + 5;
const ll INF = 1e18 + 5;
 
struct TLine
{
    ll le, sl;
    int id;
};
vector<TLine> all;
 
unordered_map<ll, ll> mp;
 
void Proc(ll l, ll r, ll le)
{
    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();
        ll t = u >> 1;
        if (t >= le && !mp.count(t))
            Q.pb(t);
        mp[t] += d;
        u--;
        t = u >> 1;
         if (t >= le && !mp.count(t))
            Q.pb(t);
        mp[t] += 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, 2);
 
        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, le);
 
    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:108:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TLine>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |     for (int i = 1; i < all.size(); i++)
      |                     ~~^~~~~~~~~~~~
ogledala.cpp: In instantiation of 'Solve()::<lambda(const auto:1&, const auto:2&)> [with auto:1 = TLine; auto:2 = 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:1&, const auto:2&)>]'
/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:1&, const auto:2&)> >]'
/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:1&, const auto:2&)> >]'
/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:1&, const auto:2&)> >]'
/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:1&, const auto:2&)> >]'
/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:1&, const auto:2&)>]'
ogledala.cpp:103:11:   required from here
ogledala.cpp:102:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  102 |              return i.le > j.le || i.le == j.le && i.id < j.id;
      |                                    ~~~~~~~~~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 62 ms 2568 KB Output is correct
4 Correct 55 ms 2752 KB Output is correct
5 Correct 87 ms 9564 KB Output is correct
6 Correct 77 ms 10672 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 640 KB Output is correct
2 Correct 39 ms 660 KB Output is correct
3 Correct 1233 ms 199824 KB Output is correct
4 Correct 1238 ms 199756 KB Output is correct
5 Correct 1364 ms 199560 KB Output is correct
6 Correct 1342 ms 199576 KB Output is correct

Subtask #3
0 / 59.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2413 ms 100624 KB Output is correct
2 Correct 2300 ms 101868 KB Output is correct
3 Execution timed out 4081 ms 200188 KB Time limit exceeded
4 Halted 0 ms 0 KB -