제출 #1244458

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1244458		1073741824	새로운 문제 (POI11_met)	C++20	0 / 100	441 ms	13860 KiB

met

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll zero=0;
const ll mod=998244353;
//const ll C=131;
//const ll inf=1e17;
const int len=300;
const int t=4;
#define Fi first
#define Se second
#define PB push_back
#define P pair<ll,ll>
#define ppl pair<P,ll>
#define LB lower_bound
#define UB upper_bound
#define SZ size()
#define BE begin()
#define EN end()
#define CON continue
#define RB rbegin()
#define EM empty()
struct BIT{
    vector<ll> bit;
    int sz;
    void init(int N){
        bit.resize(N+2);
        sz=N+1;
        for(int i=0;i<=N;i++){
            bit[i]=0;
        }
    }
    void ins(int p,ll x){
        for(;p<=sz;p+=p&-p){
            bit[p]+=x;
        }
    }
    ll prS(int p){
        ll out=0;
        for(;p;p-=p&-p){
            out+=bit[p];
        }
        return out;
    }
}Bit;
struct QQ{
    int L,R;
    vector<int>num;
};
int M,K,Q,Y,X,big,N,T,now,H,S=0;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<ll>>sta;
queue<QQ>pool;
vector<ll>need;
int l[300005],r[300005];
ll v[300005];
int ans[300005]={};
int  main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>N>>M;
    need.resize(N+1);
    sta.resize(N+1);
    for(int i=1;i<=M;i++){
            int x;
        cin>>x;
        sta[x].PB(i);
    }
    for(int i=1;i<=N;i++){
        cin>>need[i];
    }
    cin>>Q;
    for(int i=1;i<=Q;i++){
        cin>>l[i]>>r[i]>>v[i];
    }
    QQ ini;
    ini.L=1;
    ini.R=Q+1;
    for(int i=1;i<=N;i++){
        ini.num.PB(i);
    }
    int nd=0;
    pool.push(ini);
    Bit.init(N);
    while(pool.SZ){
        QQ A=pool.front();
        pool.pop();
        if(A.num.empty()){
            //cout<<"wrong";
            CON;
        }
        if(A.L>=A.R){
            for(int x:A.num){
                ans[x]=A.R;
            }
            CON;
        }
        int mm=A.L+A.R>>1;

        if(mm<nd){
            nd=0;
            Bit.init(N);
        }
        for(;nd<mm;nd++){
            if(l[nd+1]<=r[nd+1]){
                Bit.ins(l[nd+1],v[nd+1]);
                Bit.ins(r[nd+1]+1,-v[nd+1]);
            }else{
                Bit.ins(1,v[nd+1]);
                Bit.ins(l[nd+1],v[nd+1]);
                Bit.ins(r[nd+1]+1,-v[nd+1]);
            }
        }
        QQ small,big;
        small.L=A.L;
        small.R=mm;
        big.L=mm+1;
        big.R=A.R;
        ll cnt[N+1]={};
        for(int x:A.num){
            for(int p:sta[x]){
                cnt[x]+=Bit.prS(p);
            }
        }
        for(int x:A.num){
            if(cnt[x]>=need[x]){
                small.num.PB(x);
            }else{
                big.num.PB(x);
            }
        }
        /*
        cout<<endl<<mm<<":"<<endl<<endl;
        for(int x:A.num){
            cout<<x<<" ";
        }
        cout<<endl;
        for(int x:A.num){
            cout<<cnt[x]<<" ";
        }
        cout<<endl;
        */
        pool.push(small);
        pool.push(big);
    }
    for(int i=1;i<=N;i++){

        if(ans[i]>Q){
            cout<<"NIE\n";
        }else
            cout<<ans[i]<<'\n';
    }
}
/*
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
*/

• 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