Submission #1310220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310220		abadname1001	Meteors (POI11_met)	C++20	100 / 100	5830 ms	63692 KiB

met

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
int n,m,k;
const int INF = 1e9+7;
const int maxn=3e5;
int mang[maxn+7];
int goal[maxn+7];
int st[4*maxn+7];
int lazy[4*maxn+7];
vector<int>state[maxn+7];
struct node{
    int l,r,val;
};
node query[maxn+7];
pair<int,int>range[maxn+7];
vector<int>candidate[maxn+7];
void push(int id,int l,int r){
    if(lazy[id] != 0){
        if(l != r){
            lazy[id<<1] = min(lazy[id<<1] + lazy[id], INF);
            lazy[id<<1|1] = min(lazy[id<<1|1] + lazy[id], INF);
        }
        else{
            st[id] = min(st[id] + lazy[id],INF);
        }
        lazy[id] = 0;
    }
}
void update(int id,int l,int r,int u,int v,int val){
    push(id,l,r);
    if(l > v || r < u)return;
    if(l >= u && r <= v){
        lazy[id] += val;
        push(id,l,r);
        return;
    }
    int mid = (l + r)/2;
    update(id<<1,l,mid,u,v,val);
    update(id<<1|1,mid+1,r,u,v,val);
}
int get(int id,int l,int r,int u){
    push(id,l,r);
    if(l > u || r < u)return 0;
    if(l == u && r == u)return st[id];
    int mid = (l + r)/2;
    return max(get(id<<1,l,mid,u),get(id<<1|1,mid+1,r,u));
}
void input(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>mang[i];
    }
    for(int i=1;i<=n;i++){
        cin>>goal[i];
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        cin>>query[i].l>>query[i].r>>query[i].val;
    }
}
void solve(){
    for(int i=1;i<=m;i++){
        state[mang[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        range[i].first = 1;
        range[i].second = k + 1;
    }
    while(true){
        bool Update = 0;
        for(int i = 1;i <= n;i++){
            if(range[i].first < range[i].second){
                Update = 1;
                int mid = (range[i].first + range[i].second) / 2;
                candidate[mid].push_back(i);
            }
        }
        if(!Update)break;
        for(int i=1;i<=k;i++){
            if(query[i].l > query[i].r){
                update(1,1,m,query[i].l,m,query[i].val);
                update(1,1,m,1,query[i].r,query[i].val);
            }
            else update(1,1,m,query[i].l,query[i].r,query[i].val);
            for(int cur:candidate[i]){
                int res=0;
                for(int pos:state[cur]){
                    res = min(res + get(1,1,m,pos),INF);
                    if(res == INF)break;
                }
                if(res >= goal[cur])range[cur].second = i;
                else range[cur].first = i + 1;
            }
            candidate[i].clear();
        }
        for(int i=1;i<=4*m;i++){
            st[i] = 0;
            lazy[i] = 0;
        }
    }
    for(int i=1;i<=n;i++){
        if(range[i].second == k + 1)cout<<"NIE"<<endl;
        else cout<<range[i].second<<endl;
    }
}
signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    input();
    solve();
    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: 13 / 13