oj.uz

답안 #876596

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876596 2023-11-22T03:56:00 Z CYhuang Meteors (POI11_met) C++17
100 / 100
 1246 ms 33816 KB 
#include<bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long

#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)

typedef pair<int,int> pii;
#define F first
#define S second

typedef vector<int> vi;
#define pb push_back
#define ft front()
#define bk back()
#define tp top()
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define ms(a,x) memset(a,x,sizeof(a))
const int Size=3e5;
int m;
int p[Size+20],ans[Size+20],bit[Size+20];
vi own[Size+20];
struct Query{
    int l,r,val;
}qq[Size+20];
int lowbit(int x){
    return x&(-x);
}
void modify(int x,int val){
    while(x<=Size){
        bit[x]+=val;
        x+=lowbit(x);
    }
}
int query(int x){
    int tot=0;
    while(x){
        tot+=bit[x];
        x-=lowbit(x);
    }
    return tot;
}
void range_modify(int l,int r,int val){
    if(l<=r) modify(l,val),modify(r+1,-val);
    else{
        modify(l,val),modify(m+1,-val);
        modify(1,val),modify(r+1,-val);
    }
}
void check(vi &qry,vi &ok,vi &fail){
    for(auto i:qry){
        int tot=0;
        for(auto j:own[i]){
            tot+=query(j);
            if(p[i]<=tot)   break;
        }
        if(p[i]<=tot)   ok.pb(i);
        else{
            p[i]-=tot;
            fail.pb(i);
        }
    }
    vi().swap(qry);
}
void total_bs(vi &qry,int ll,int rr){
    if(!sz(qry))    return ;
    if(ll==rr){
        for(auto i:qry) ans[i]=ll;
        return ;
    }
    int mm=ll+((rr-ll)>>1);
    For(i,ll,mm)    range_modify(qq[i].l,qq[i].r,qq[i].val);
    vi ok,fail;
    check(qry,ok,fail);
    For(i,ll,mm)    range_modify(qq[i].l,qq[i].r,-qq[i].val);
    total_bs(ok,ll,mm);
    total_bs(fail,mm+1,rr);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n>>m;
    vi vec;
    For(i,1,m){
        int o;
        cin>>o;
        own[o].pb(i);
    }
    For(i,1,n){
        cin>>p[i];
        vec.pb(i);
    }
    int k;
    cin>>k;
    For(i,1,k)  cin>>qq[i].l>>qq[i].r>>qq[i].val;
    total_bs(vec,1,k+1);
    For(i,1,n){
        if(ans[i]<=k)  cout<<ans[i]<<"\n";
        else    cout<<"NIE\n";
    }
    return 0;
}
/*
check:
1.read problem statement correctly
2.int overflow
3.array out of bound
4.special case(0 or 1)
5.time complexity
6.try to change dimension in array!!!
*/

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 15708 KB Output is correct
2 Correct 87 ms 18388 KB Output is correct
3 Correct 80 ms 16084 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 15956 KB Output is correct
2 Correct 110 ms 15892 KB Output is correct
3 Correct 52 ms 18404 KB Output is correct
4 Correct 18 ms 13916 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 15704 KB Output is correct
2 Correct 118 ms 18260 KB Output is correct
3 Correct 40 ms 14936 KB Output is correct
4 Correct 78 ms 16096 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 15316 KB Output is correct
2 Correct 125 ms 16100 KB Output is correct
3 Correct 43 ms 15452 KB Output is correct
4 Correct 106 ms 18312 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 29000 KB Output is correct
2 Correct 148 ms 21588 KB Output is correct
3 Correct 264 ms 19028 KB Output is correct
4 Correct 926 ms 32264 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 324 ms 28584 KB Output is correct
2 Correct 209 ms 21460 KB Output is correct
3 Correct 83 ms 19120 KB Output is correct
4 Correct 1246 ms 33816 KB Output is correct