Submission #1280058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280058		andrei_iorgulescu	팀들 (IOI15_teams)	C++20	34 / 100	4103 ms	196556 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

using integer = int;
#define int long long

struct DS
{
    int n;
    vector<pair<int, int>> a;
    vector<int> v;
    vector<vector<int>> aint;

    void init(int N, vector<pair<int, int>> A)
    {
        n = N;
        a = A;
        v.resize(n);
        sort(a.begin(), a.end());
        for (int i = 0; i < n; i++)
            v[i] = a[i].second;
        aint.resize(4 * n + 5);
        for (int i = 0; i < n; i++)
            aint[1].push_back(i);
        build(1, 1, n);
    }

    void build(int nod, int vl, int vr)
    {
        if (vl == vr)
            return;
        int mij = (vl + vr) / 2;
        for (auto it : aint[nod])
        {
            if (v[it] <= mij)
                aint[2 * nod].push_back(it);
            else
                aint[2 * nod + 1].push_back(it);
        }
        build(2 * nod, vl, mij);
        build(2 * nod + 1, mij + 1, vr);
    }

    int query(int nod, int vl, int vr, int stt, int drr, int k)
    {
        if (vl == vr)
            return vl;
        int mij = (vl + vr) / 2;
        int st = -1, pas = 1 << 19;
        while (pas != 0)
        {
            if (st + pas < aint[2 * nod].size() and aint[2 * nod][st + pas] <= drr)
                st += pas;
            pas /= 2;
        }
        int rr = st;
        st = aint[2 * nod].size(), pas = 1 << 19;
        while (pas != 0)
        {
            if (st - pas >= 0 and aint[2 * nod][st - pas] >= stt)
                st -= pas;
            pas /= 2;
        }
        int ll = st;
        if (rr - ll + 1 >= k)
            return query(2 * nod, vl, mij, stt, drr, k);
        else
            return query(2 * nod + 1, mij + 1, vr, stt, drr, k - max(0ll, (rr - ll + 1)));
    }

    pair<int, int> getgood(int l, int r)
    {
        int st = -1, pas = 1 << 19;
        while (pas != 0)
        {
            if (st + pas < n and a[st + pas].first <= r)
                st += pas;
            pas /= 2;
        }
        int rr = st;
        st = n, pas = 1 << 19;
        while (pas != 0)
        {
            if (st - pas >= 0 and a[st - pas].first >= l)
                st -= pas;
            pas /= 2;
        }
        int ll = st;
        return {ll, rr};
    }

    int query_kth(int l, int r, int k)
    {
        pair<int, int> lprp = getgood(l, r);
        l = lprp.first;
        r = lprp.second;
        if (r - l + 1 <= k)
            return n + 1;
        return query(1, 1, n, l, r, k);
    }
};

struct DS2
{
    int n;
    vector<pair<int, int>> a;

    void init(int N, vector<pair<int, int>> A)
    {
        n = N;
        a = A;
    }

    int cate_incl(int l, int r)
    {
        int ct = 0;
        for (auto it : a)
        {
            if (it.first >= l and it.second <= r)
                ct++;
        }
        return ct;
    }
};

DS wavelet;
DS2 pst;
int n;

void init(integer N, integer A[], integer B[])
{
    n = N;
    vector<pair<int, int>> a;
    for (int i = 0; i < N; i++)
        a.push_back({A[i], B[i]});
    wavelet.init(n, a);
    pst.init(n, a);
}

integer can(integer M, integer K[])
{
    int m = M, sm = 0;
    map<int, int> mp;
    for (int i = 0; i < m; i++)
    {
        mp[K[i]] += K[i], sm += K[i];
    }
    if (sm > n)
        return 0;
	vector<pair<int, int>> a;
	for (auto it : mp)
        a.push_back(it);
    a.push_back({0, 0});
    sort(a.begin(), a.end());///probabil era deja sortat dar idk
    set<int> s;
    vector<int> dp(a.size());
    dp[0] = 0;
    s.insert(0);
    set<pair<int, int>> bang;
    int ans = n;
    for (int i = 1; i < a.size(); i++)
    {
        while (!bang.empty())
        {
            pair<int, int> it = *bang.begin();
            if (it.first >= a[i].first)
                break;
            bang.erase(it);
            int xx = *s.upper_bound(it.second);
            int zz = it.second;
            s.erase(xx);
            if (s.upper_bound(it.second) != s.end())
            {
                int yy = *s.upper_bound(it.second);
                bang.erase({wavelet.query_kth(a[xx].first + 1, a[yy].first, dp[yy] - dp[xx]), xx});
                bang.insert({wavelet.query_kth(a[zz].first + 1, a[yy].first, dp[yy] - dp[zz]), zz});
            }
        }
        int cn = *s.rbegin();
        dp[i] = a[i].second + dp[cn] + pst.cate_incl(a[cn].first + 1, a[i].first - 1);
        bang.insert({wavelet.query_kth(a[cn].first + 1, a[i].first, dp[i] - dp[cn]), cn});
        ans = max(ans, dp[i] + pst.cate_incl(a[i].first + 1, n));
        s.insert(i);
    }
    if (ans > n)
        return 0;
    else
        return 1;
}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 0 / 43
• Subtask 4: 0 / 23