oj.uz

Submission #642129

# Submission time Handle Problem Language Result Execution time Memory
642129 2022-09-18T14:51:25 Z messiuuuuu OGLEDALA (COI15_ogledala) C++14
19 / 100
 1465 ms 524288 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;

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];
pair<int, int> con[MAXN][100];
map<ll, int> mp1[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);

        int cnt = 0;

        for (const auto& p : mp)
        {
            all.pb({p.fi, p.se, i});
            ll num = p.fi;
            mp1[i][num] = ++cnt;
            con[i][mp1[i][num]] = make_pair(mp1[i][num / 2], mp1[i][(num - 1) / 2]);
        }

        last = a[i];
    }
}

ll sum[MAXN * 100];
ll res;
int ID;
ll cal[100];

void Cal(ll l, ll r, int le)
{
    memset(cal, 0, sizeof(cal));
    if (l > r)
        return;
    deque<int> Q;
    cal[mp1[ID][r - l + 1]] = 1;
    Q.pb(mp1[ID][r - l + 1]);
    int cnt = 0;
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop_front();
        int t = con[ID][u].fi;
        if (t >= le && !cal[t])
            Q.pb(t);
        cal[t] += cal[u];
        t = con[ID][u].se;
        if (t >= le && !cal[t])
            Q.pb(t);
        cal[t] += cal[u];
    }
    if (m > 3e5 && n > 5e4)
        assert(1 < 0);
}

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;
    Cal(l, mid - 1, mp1[ID][le]);

    if (sl <= cal[mp1[ID][le]])
    {
        Dnc(l, mid - 1, le, sl);
    } else
    {
        sl -= cal[mp1[ID][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;
        ID = all[p].id;
        Dnc(b[ID].fi, b[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 Cal(long long int, long long int, int)':
ogledala.cpp:94:9: warning: unused variable 'cnt' [-Wunused-variable]
   94 |     int cnt = 0;
      |         ^~~
ogledala.cpp: In function 'void Solve()':
ogledala.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TLine>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     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:137:11:   required from here
ogledala.cpp:136:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  136 |              return i.le > j.le || i.le == j.le && i.id < j.id;
      |                                    ~~~~~~~~~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ogledala.cpp:174:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5164 KB Output is correct
2 Correct 3 ms 5076 KB Output is correct
3 Correct 63 ms 18180 KB Output is correct
4 Correct 58 ms 18956 KB Output is correct
5 Correct 135 ms 105992 KB Output is correct
6 Correct 139 ms 110480 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5720 KB Output is correct
2 Correct 17 ms 5692 KB Output is correct
3 Runtime error 1112 ms 524288 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #3
0 / 59.0

# Verdict Execution time Memory Grader output
1 Runtime error 1465 ms 524288 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -