Submission #1176308

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176308		bestbest	Meteors (POI11_met)	C++20	87 / 100	911 ms	65100 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+1;

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

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


void update(int val,int idx){
    for(;idx<N;idx+=(idx&-idx)){
        if(fen[idx]>(ll)1e9 && val>0)continue;
        fen[idx]+=val;
    }
}


int query(int idx){
    rufen=0;
    for(;idx>0;idx-=(idx&-idx)){
        rufen+=fen[idx];
        if(rufen>(ll)1e9)break;
    }
    return rufen;
}


int main(){Linux
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> a;
        prop[a].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;


    while(1){
        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)break;

        for(int i=1;i<=m;i++)fen[i]=0;

        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);

            }
            for(int v:res[i]){
                ll sum=0;
                bool mor=0;
                for(int c:prop[v]){
                    sum+=query(c);
                    if(sum>(ll)1e9){
                        mor=1;
                        break;
                    }
                }
                if(mor || sum>=want[v])r[v]=mid[v];
                else l[v]=mid[v]+1;

            }
    
        }
    }



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


    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: 13 / 13
• Subtask 8: 0 / 13