Submission #1174228

#	Time	Username	Problem	Language	Result	Execution time	Memory
1174228		adkjt	Meteors (POI11_met)	C++20	0 / 100	751 ms	35256 KiB

met

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
vector<int> own[333333];
int mid[333333],l[333333],r[333333],lim[333333],fen[333333],val[333333];
pair<pair<int,int>,int> meteor[333333];
vector<int> ask[333333];
void update(int idx,int v)
{
    while(idx<=3e5+64)
    {
        fen[idx]+=v;
        idx+=idx&-idx;
    }
}
int read(int idx)
{
    int sum=0;
    while(idx>0)
    {
        sum+=fen[idx];
        idx-=idx&-idx;
    }
    return sum;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x;
        cin>>x;
        own[x].push_back(i);
    }
    for(int i=1; i<=n; i++)
    {
        cin>>lim[i];

    }
    int k;
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        cin>>meteor[i].f.f>>meteor[i].f.s>>meteor[i].s;
    }
    for(int i=1; i<=n; i++)
        l[i]=1,r[i]=k+1;

    int cnt=0;
    while(cnt<n)
    {
        cnt=0;
        for(int i=1;i<=k;i++)
            ask[i].clear();

        memset(fen,0,sizeof fen);
        for(int i=1; i<=n; i++)
        {
            if(l[i]>=r[i])
            {
                cnt++;
                continue;
            }
            mid[i]=(l[i]+r[i])/2;
            if(mid[i]>k)
            {
                cnt++;
                continue;
            }
            ask[mid[i]].push_back(i);
        }
        for(int i=1; i<=k; i++)
        {
            if(meteor[i].f.f<=meteor[i].f.s)
            {
                update(meteor[i].f.f,meteor[i].s);
                update(meteor[i].f.s+1,-meteor[i].s);
            }
            else
            {
                update(meteor[i].f.f,meteor[i].s);
                update(m+1,-meteor[i].s);
                update(1,meteor[i].s);
                update(meteor[i].f.s+1,-meteor[i].s);
            }

            for(auto x:ask[i])
            {
                int sum=0;
                for(auto y:own[x])
                {
                    sum+=read(y);
                }
                if(sum>=lim[x]) r[x]=mid[x],val[x]=1;
                else l[x]=mid[x]+1;
            }
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(!val[i]) cout<<"NIE\n";
        else
            cout<<mid[i]<<'\n';
    }
}

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