Submission #1224794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224794		TitanicXDzz	Meteors (POI11_met)	C++20	24 / 100	3 ms	1452 KiB

met

#include<bits/stdc++.h>
using namespace std;
int a[1010];
int l[1010];
int r[1010];
int ll[1010];
int rr[1010];
int val[1010];
vector<int> v[1010];
queue<int> q[1010];
long long sumi[1010];
int m;
void update(int idx,int val){
sumi[idx]+=val;
 if(idx+(idx&(-idx))<=m)
    update(idx+(idx&(-idx)),val);
 return;
}
long long read(int idx){
 if(idx-(idx&(-idx))>=1)
    return(sumi[idx]+read(idx-(idx&(-idx))));
 return(sumi[idx]);
}
signed main(){
 ios_base::sync_with_stdio(0);cin.tie(0);
 int n;
 cin>>n>>m;
 for(int i=1;i<=m;i++){
    int x;
    cin>>x;
    v[x].push_back(i);
 }
 for(int i=1;i<=n;i++)
    cin>>a[i];
 int k;
 cin>>k;
 for(int i=1;i<=k;i++){
    cin>>l[i]>>r[i]>>val[i];
 }
 for(int i=1;i<=n;i++){
    ll[i]=1;
    rr[i]=k+1;
    q[(ll[i]+rr[i])/2].push(i);
 }
 for(int iii=1;iii<=20;iii++){
    for(int i=0;i<=m+1;i++){
        sumi[i]=0;
    }
    for(int i=1;i<=k;i++){
        if(l[i]<=r[i]){
         update(l[i],val[i]);
         update(r[i]+1,-val[i]);
        }
        else{
            update(l[i],val[i]);
            update(1,val[i]);
            update(r[i]+1,-val[i]);
        }
        while(q[i].empty()==0){
            long long sumo=0;
            for(auto g:v[q[i].front()])
                sumo+=read(g);

            if(sumo<a[q[i].front()])
                ll[q[i].front()]=i+1;
            else
                rr[q[i].front()]=i;
            if(ll[q[i].front()]<rr[q[i].front()])
            q[(ll[q[i].front()]+rr[q[i].front()])/2].push(q[i].front());
            q[i].pop();
        }
    }
 }
 for(int i=1;i<=n;i++){
    if(ll[i]>k)
        cout<<"NIE\n";
    else
        cout<<ll[i]<<"\n";
 }
 return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 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