oj.uz

답안 #876592

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
876592 2023-11-22T03:51:32 Z CYhuang Meteors (POI11_met) C++17
0 / 100
 328 ms 29468 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])  if((tot+=query(j))>=p[i])   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
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 12636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Incorrect 3 ms 12636 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 15704 KB Output is correct
2 Correct 95 ms 18572 KB Output is correct
3 Incorrect 67 ms 15964 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 102 ms 15980 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 88 ms 15708 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 15512 KB Output is correct
2 Correct 121 ms 15872 KB Output is correct
3 Incorrect 48 ms 15640 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 327 ms 29468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 328 ms 28412 KB Output isn't correct
2 Halted 0 ms 0 KB -