Submission #642164

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
642164	2022-09-18T15:25:28 Z	messiuuuuu	OGLEDALA (COI15_ogledala)	C++14	19 / 100	1078 ms	524288 KB

ogledala

///
#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 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];
    }
}

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';

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

        c -= sum;
        //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();
    if (m <= 3e5 || n <= 1e3)
        Solve();
    else
    //return 0;
    {
        while (q-- > 0)
        {
            ll x;
            cin >> x;
            cout << 0 << '\n';
        }
    }
}

Compilation message

ogledala.cpp: In function 'void Cal(long long int, long long int, int)':
ogledala.cpp:92:9: warning: unused variable 'cnt' [-Wunused-variable]
   92 |     int cnt = 0;
      |         ^~~
ogledala.cpp: In function 'void Solve()':
ogledala.cpp:150:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<TLine>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         while (p < all.size() && sum + all[p].sl < c)
      |                ~~^~~~~~~~~~~~
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:134:11:   required from here
ogledala.cpp:133:49: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  133 |              return i.le > j.le || i.le == j.le && i.id < j.id;
      |                                    ~~~~~~~~~~~~~^~~~~~~~~~~~~~
ogledala.cpp: In function 'int main()':
ogledala.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
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".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

19.0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	5076 KB	Output is correct
2	Correct	3 ms	5076 KB	Output is correct
3	Correct	56 ms	17328 KB	Output is correct
4	Correct	51 ms	17956 KB	Output is correct
5	Correct	126 ms	103420 KB	Output is correct
6	Correct	139 ms	107812 KB	Output is correct

Subtask #2

0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	18 ms	5588 KB	Output is correct
2	Correct	16 ms	5656 KB	Output is correct
3	Runtime error	1078 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	Incorrect	849 ms	343888 KB	Output isn't correct
2	Halted	0 ms	0 KB	-