Submission #1176287

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176287		bestbest	Meteors (POI11_met)	C++20	87 / 100	1257 ms	66336 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,p;
};

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


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


ll query(int idx){
    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;
        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;

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

            }
            // cout << "fen ";
            // for(int i=1;i<=m;i++)cout << query(i) << sp;
            // cout << en;
            for(int v:res[i]){
                cur=0;
                mor=0;
                // cout << v << ':' << sp;
                for(int c:prop[v]){
                    cur+=query(c);
                    if(cur>ll(1e9)){
                        mor=1;
                        break;
                    }
                }
                // cout << "sum" << sum << en;
                if(mor || cur>=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 << "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