제출 #1176268

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176268		bestbest	Meteors (POI11_met)	C++20	0 / 100	905 ms	69968 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define  en '\n'
#define  sp ' '
typedef long long ll;
#define Linux ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pii pair<int,int>


const int N=3e5+10;

struct stu
{
    int s,e;
    ll p;
};



int n,m,k;
ll fen[N*2],a[N];
bool chk=1,sub;
ll want[N];
stu met[N];
int l[N],r[N],mid[N];
vector<int> res[N],prop[N];


void update(ll val,int idx){
    for(;idx<N;idx+=(idx&-idx)){
        fen[idx]+=val;
    }
}


int query(int idx){
    ll sum=0;
    for(;idx>0;idx-=(idx&-idx)){
        sum+=fen[idx];
    }
    return sum;
}


int main(){Linux
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a[i];
        prop[a[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin >> want[i];
    }

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

    // for(int i=1;i<=n;i++){
    //     for(int j:prop[i])cout << j << sp;
    //     cout << en;
    // }


    while(chk){
        sub=1;
        for(int i=1;i<=k;i++){
            res[i].clear();
        }
        for(int i=1;i<=m;i++){
            mid[i]=(l[i]+r[i])/2;
            res[mid[i]].push_back(i);
            if(l[i]<r[i])sub=0;
        }
        if(sub)chk=0;
        // for(int i=1;i<=n;i++)cout << l[i] << sp << r[i] << sp;
        // cout << en;

        for(int i=1;i<=m;i++){
            update(-query(i),i);
        }

        for(int i=1;i<=k;i++){
            if(met[i].s<=met[i].e){
                update(met[i].p,met[i].s);
                update(-met[i].p,met[i].e+1);
            }
            else {
                update(-met[i].p,met[i].e+1);
                update(met[i].p,met[i].s);
                update(met[i].p,1);

            }
            // cout << "fen ";
            // for(int i=1;i<=m;i++)cout << query(i) << sp;
            // cout << en;
            for(int v:res[i]){
                ll sum=0;
                // cout << v << ':' << sp;
                for(int c:prop[v]){
                    sum+=query(c);
                    // cout << query(c) << sp;
                }
                // cout << "sum" << sum << en;
                if(sum>=want[v])r[v]=mid[v];
                else l[v]=mid[v]+1;

                // cout << en;
            }
    
        }
    }



    for(int i=1;i<=n;i++){
        if(l[i]>k)cout << "NEI\n";
        else cout << l[i] << en;
    }


    return 0;
}

• 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