oj.uz

답안 #684505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
684505 2023-01-21T11:14:08 Z bachhoangxuan Meteors (POI11_met) C++17
74 / 100
 902 ms 65536 KB 
// Judges with GCC >= 12 only needs Ofast
// #pragma GCC optimize("O3,no-stack-protector,fast-math,unroll-loops,tree-vectorize")
// MLE optimization
// #pragma GCC optimize("conserve-stack")
// Old judges
// #pragma GCC target("sse4.2,popcnt,lzcnt,abm,mmx,fma,bmi,bmi2")
// New judges. Test with assert(__builtin_cpu_supports("avx2"));
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
// Atcoder
// #pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma")
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<> pp(0.0,1.0);
#define int long long
#define pii pair<int,int>
const int inf=1e18;
const int mod=998244353;
const int maxn=300005;
const int maxl=20;
const int maxa=1000005;
int power(int a,int n){
    int res=1;
    while(n){
        if(n&1) res=res*a%mod;
        a=a*a%mod;n>>=1;
    }
    return res;
}
struct qry{
    int l,r,val;
};
int n,m,q,a[maxn],p[maxn],ans[maxn];
vector<int> x[maxn],ss[maxn];
qry que[maxn];
namespace BIT{
    int bit[maxn];
    void update(int l,int r,int val){
        for(int i=l;i<=m;i+=(i&(-i))) bit[i]+=val;
        for(int i=r+1;i<=m;i+=(i&(-i))) bit[i]-=val;
    }
    void up(int l,int r,int val){
        if(l>r){update(l,m,val);update(1,r,val);}
        else update(l,r,val);
    }
    int query(int x){
        int res=0;
        for(int i=x;i>=1;i-=(i&(-i))) res+=bit[i];
        return res;
    }
}
void cal(int l,int r){
    int mid=(l+r)>>1,lt=(l+mid-1)>>1,rt=(mid+r+1)>>1;
    for(int v:ss[mid]){
        int sum=0;
        for(int d:x[v]) sum=min(sum+BIT::query(d),inf);
        if(sum>=p[v]) ans[v]=mid;
        if(sum>=p[v] && l<mid) ss[lt].push_back(v);
        else if(sum<p[v] && r>mid) ss[rt].push_back(v);
    }
    if(r>mid){
        for(int i=mid+1;i<=rt;i++) BIT::up(que[i].l,que[i].r,que[i].val);
        cal(mid+1,r);
        for(int i=mid+1;i<=rt;i++) BIT::up(que[i].l,que[i].r,-que[i].val);
    }
    if(l<mid){
        for(int i=lt+1;i<=mid;i++) BIT::up(que[i].l,que[i].r,-que[i].val);
        cal(l,mid-1);
        for(int i=lt+1;i<=mid;i++) BIT::up(que[i].l,que[i].r,que[i].val);
    }
}
void solve(){
    cin >> n >> m;
    for(int i=1;i<=m;i++){cin >> a[i];x[a[i]].push_back(i);}
    for(int i=1;i<=n;i++) cin >> p[i];
    cin >> q;
    for(int i=1;i<=q;i++) cin >> que[i].l >> que[i].r >> que[i].val;
    int mid=(1+q)>>1;
    for(int i=1;i<=n;i++) ss[mid].push_back(i);
    for(int i=1;i<=mid;i++) BIT::up(que[i].l,que[i].r,que[i].val);
    cal(1,q);
    for(int i=1;i<=n;i++){
        if(ans[i]) cout << ans[i] << '\n';
        else cout << "NIE\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int t=1;//cin >> t;
    while(t--) solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 14504 KB Output is correct
2 Correct 9 ms 14552 KB Output is correct
3 Correct 8 ms 14568 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 61 ms 17928 KB Output is correct
2 Correct 93 ms 21492 KB Output is correct
3 Correct 76 ms 20476 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 19296 KB Output is correct
2 Correct 82 ms 19680 KB Output is correct
3 Correct 95 ms 21708 KB Output is correct
4 Correct 31 ms 18580 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 18332 KB Output is correct
2 Correct 80 ms 22232 KB Output is correct
3 Correct 41 ms 16164 KB Output is correct
4 Correct 80 ms 21140 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 17080 KB Output is correct
2 Correct 87 ms 19268 KB Output is correct
3 Correct 62 ms 17868 KB Output is correct
4 Correct 91 ms 23084 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 902 ms 49308 KB Output is correct
2 Correct 661 ms 29264 KB Output is correct
3 Correct 187 ms 20948 KB Output is correct
4 Runtime error 749 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 837 ms 47424 KB Output is correct
2 Correct 690 ms 29172 KB Output is correct
3 Correct 157 ms 19640 KB Output is correct
4 Runtime error 784 ms 65536 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -