Submission #1189086

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189086		prideliqueee	Meteors (POI11_met)	C++20	74 / 100	3873 ms	44544 KiB

met

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define f first
#define s second
int lz[1200000];
int cnt[1200000];
struct st
{
    int l,r,x;
};
void pushlz(int l,int r,int i)
{
    cnt[i]+=lz[i];
    if(l!=r)
    {
        lz[i*2]+=lz[i];
        lz[i*2+1]+=lz[i];
    }
    lz[i]=0;
}
void update(int l,int r,int i,int ql,int qr,int val)
{
    pushlz(l,r,i);
    if(qr<l||ql>r)
    return;
    if(ql<=l&&qr>=r)
    {
        lz[i]+=val;
        pushlz(l,r,i);
        return;
    }
    int mid=(l+r)/2;
    update(l,mid,i*2,ql,qr,val);
    update(mid+1,r,i*2+1,ql,qr,val);
}
int ans;
void query(int l,int r,int i,int index)
{
    pushlz(l,r,i);
    if(index<l||index>r)
    return;
    if(l==r)
    {
        ans=cnt[i];
        return;
    }
    int mid=(l+r)/2;
    query(l,mid,i*2,index);
    query(mid+1,r,i*2+1,index);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
    cin>>n>>m;
    vector<int> p[300010];
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        p[x].push_back(i);
    }
    int a[n+1],ll[n+1],rr[n+1];
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int k;
    cin>>k;
    for(int i=1;i<=n;i++)
    {
        ll[i]=0;
        rr[i]=k+1;
    }
    st e[k+1];
    for(int i=1;i<=k;i++)
    {
        int l,r,x;
        cin>>l>>r>>x;
        e[i]={l,r,x};
    }
    int bb=1;
    while(bb)
    {
        bb=0;
        vector<pair<int,int>> qq;
        for(int i=1;i<=n;i++)
        {
            if(ll[i]<rr[i])
            {
                bb=1;
                qq.push_back({(ll[i]+rr[i])/2,i});
            }
        }
        if(!bb)
        break;
        sort(qq.begin(),qq.end());
        int j=1;
        memset(cnt,0,sizeof cnt);
        memset(lz,0,sizeof lz);
        for(int i=0;i<qq.size();i++)
        {
            int mid=qq[i].f,index=qq[i].s;
            while(j<=k&&j<=mid)
            {
                int l=e[j].l,r=e[j].r,x=e[j].x;
                j++;
                if(l<=r)
                {
                    update(1,m,1,l,r,x);
                }
                else
                {
                    update(1,m,1,l,m,x);
                    update(1,m,1,1,r,x);
                }
            }
            int sum=0;
            for(auto y:p[index])
            {
                query(1,m,1,y);
                sum+=ans;
            }
            if(sum>=a[index])
            {
                rr[index]=mid;
            }
            else
            {
                ll[index]=mid+1;
            }
            //cout<<index<<" "<<sum<<" "<<mid<<endl;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(ll[i]==k+1)
        cout<<"NIE"<<'\n';
        else
        cout<<ll[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: 0 / 13
• Subtask 8: 0 / 13