제출 #1192640

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192640		vukhacminh	새로운 문제 (POI11_met)	C++20	74 / 100	823 ms	84064 KiB

met

/**
*    Author :  Vu Khac Minh
**/
#include <bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int maxn = 3e5 + 5;
const int mod = 1e9+7;
int n,m,l[maxn],r[maxn],ctry[maxn],k,res[maxn];
struct node
{
    int l,r,c;
}rain[maxn];
vector<int> tocheck[maxn],a[maxn];
ll bit[4*maxn];
void add(int u,ll val)
{
    for(;u<=m+1;u+=u&-u) bit[u]+=val;
}
ll get(int u)
{
    ll s = 0;
    for(;u;u-=u&-u) s+=bit[u];
    return s;
}
void rangeadd(int l,int r,ll val)
{
    add(l,val);
    add(r+1,-val);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i =1;i<=m;i++)
    {
        int p;
        cin>>p;
        a[p].push_back(i);
    }
    for(int i =1;i<=n;i++) cin>>ctry[i];
    cin>>k;
    for(int i=1;i<=k;i++)
    {
        int L,R,C;
        cin>>L>>R>>C;
        rain[i] = {L,R,C};
    }
    for(int i =1;i<=n;i++)
    {
        l[i] = 1;
        r[i] = k;
        res[i] = -1;
    }
    while(true)
    {
        bool check = false;
        for(int i =1;i<=k;i++) tocheck[i].clear();
        for(int i =1;i<=n;i++)
        {
            if(l[i]<=r[i])
            {
                int mid = (l[i] + r[i]) >>1;
                tocheck[mid].push_back(i);
                check  = true;
            }
        }
        if(!check) break;
        fill(bit,bit + m + 5, 0);
        for(int i =1;i<=k;i++)
        {
            int L= rain[i].l, R = rain[i].r, C = rain[i].c;
            if(L<=R) rangeadd(L,R,C);
            else
            {
                rangeadd(L,m,C);
                rangeadd(1,R,C);
            }
            for(auto id : tocheck[i])
            {
                ll tol = 0;
                for(auto j : a[id])
                {
                    tol+=get(j);
                    if(tol>=ctry[id]) break;
                }
                if(tol>=ctry[id])
                {
                    r[id] = i-1;
                    res[id] = i;
                }
                else l[id] = i+1;
            }
        }
    }
    for(int i =1;i<=n;i++)
    {
        if(res[i] == -1) cout<<"NIE"<<'\n';
        else cout<<res[i]<<'\n';
    }
    return 0;
}

• 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