제출 #1337080

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1337080		alexdd	Exhibition 3 (JOI25_exhibition3)	C++20	28 / 100	3095 ms	2648 KiB

Main

#include <bits/stdc++.h>
using namespace std;

int n;
namespace SQRT_DS
{
    int tole[100005], tori[100005];
    const int BUC = 350;
    void init()
    {
        for(int i=0;i<=n;i++)
        {
            tole[i] = -1;
            tori[i] = n+1;
        }
    }
    int cntle(int x)
    {
        int cnt = 0;
        while(x >= 0)
        {
            x = tole[x];
            cnt++;
        }
        return cnt - 1;
    }
    int cntri(int x)
    {
        int cnt = 0;
        while(x <= n)
        {
            x = tori[x];
            cnt++;
        }
        return cnt - 1;
    }
    int when_added(int le, int ri)
    {
        le--;

        return cntle(le) + 1 + cntri(ri);
    }
    void add(int le, int ri)
    {
        le--;

        for(int i=le;i>=0;i--)
        {
            if(tori[i] > ri)
                tori[i] = ri;
            else
                break;
        }
        for(int i=ri;i<=n;i++)
        {
            if(tole[i] < le)
                tole[i] = le;
            else
                break;
        }
    }
}

int m;
int fr[100005];
pair<int,int> v[100005];
int rez[100005];
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    int a;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        fr[a]++;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>v[i].first>>v[i].second;
        rez[i] = -1;
    }
    for(int val=n;val>=1;val--)
    {
        if(fr[val] == 0)
            continue;
        SQRT_DS::init();
        for(int i=1;i<=m;i++)
        {
            if(rez[i] != -1)
                continue;
            if(SQRT_DS::when_added(v[i].first, v[i].second) <= fr[val])
            {
                rez[i] = val;
                SQRT_DS::add(v[i].first, v[i].second);
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        assert(rez[i] != -1);
        cout<<rez[i]<<"\n";
    }
    return 0;
}

/*



*/

• Subtask 1: 0 / 0
• Subtask 2: 19 / 19
• Subtask 3: 9 / 9
• Subtask 4: 0 / 19
• Subtask 5: 0 / 12
• Subtask 6: 0 / 17
• Subtask 7: 0 / 24