제출 #1333985

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1333985		kenkunkin	새로운 문제 (POI11_met)	C++20	100 / 100	933 ms	59736 KiB

met

#include <bits/stdc++.h>

using namespace std;

void Init()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

typedef long long ll;

const int maxn=300000+5;

int n,m,k;

int o[maxn];
ll p[maxn];

vector<int> pos[maxn];
vector<int> bucket[maxn];

int L[maxn],R[maxn],ans[maxn];

int l[maxn],r[maxn];
ll a[maxn];

ll bit[maxn];

void resetBIT()
{
    for(int i=1;i<=m;i++)
        bit[i]=0;
}

void add(int i,ll v)
{
    for(;i<=m;i+=i&-i)
        bit[i]+=v;
}

ll sum(int i)
{
    ll s=0;
    for(;i;i-=i&-i)
        s+=bit[i];
    return s;
}

void update(int L,int R,ll val)
{
    if(L<=R)
    {
        add(L,val);
        add(R+1,-val);
    }
    else
    {
        add(L,val);
        add(m+1,-val);
        add(1,val);
        add(R+1,-val);
    }
}

int main()
{
    Init();

    cin>>n>>m;

    for(int i=1;i<=m;i++)
    {
        cin>>o[i];
        pos[o[i]].push_back(i);
    }

    for(int i=1;i<=n;i++)
        cin>>p[i];

    cin>>k;

    for(int i=1;i<=k;i++)
        cin>>l[i]>>r[i]>>a[i];

    for(int i=1;i<=n;i++)
    {
        L[i]=1;
        R[i]=k;
        ans[i]=-1;
    }

    while(true)
    {
        bool done=true;

        for(int i=1;i<=k;i++)
            bucket[i].clear();

        for(int i=1;i<=n;i++)
        {
            if(L[i]<=R[i])
            {
                done=false;

                int mid=(L[i]+R[i])/2;

                bucket[mid].push_back(i);
            }
        }

        if(done) break;

        resetBIT();

        for(int i=1;i<=k;i++)
        {
            update(l[i],r[i],a[i]);

            for(int state:bucket[i])
            {
                ll s=0;

                for(int sector:pos[state])
                {
                    s+=sum(sector);

                    if(s>=p[state])
                        break;
                }

                if(s>=p[state])
                {
                    ans[state]=i;
                    R[state]=i-1;
                }
                else
                    L[state]=i+1;
            }
        }
    }

    for(int i=1;i<=n;i++)
    {
        if(ans[i]==-1) cout<<"NIE\n";
        else cout<<ans[i]<<"\n";
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13