oj.uz

답안 #660134

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660134 2022-11-20T12:49:45 Z beepbeepsheep Meteors (POI11_met) C++17
74 / 100
 1075 ms 36900 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long
typedef pair<ll,ll> ii;
const ll inf=1e14;
const ll maxn=3e5+5;
const ll mod=1e9+7;

vector<ll> adj[maxn];
ll arr[maxn];
ll n,e,op,ele,a,b,c;
vector<tuple<ll,ll,ll>> v;
ll fen[maxn];
void upd(ll x, ll y, ll val){
    while (x<maxn){
        fen[x]+=val;
        x+=(x&-x);
    }
    y++;
    while (y<maxn){
        fen[y]-=val;
        y+=(y&-y);
    }
}
ll query(ll p){
    ll ans=0;
    while (p){
        ans+=fen[p];
        p-=(p&-p);
    }
    return ans;
}
ll ans[maxn];
queue<tuple<ll,ll,vector<ll>>> q;
ll curr=0;
void solve(ll l, ll r, vector<ll> &pple){
    if (l==0) memset(fen,0,sizeof(fen)),curr=0; //do a reset
    if (l==r){
        for (auto u:pple) ans[u]=l; //done
        return;
    }
    ll m=(l+r)>>1;
    for (int i=curr;i<=m;i++){
        tie(a,b,c) = v[i];
        if (a<=b) upd(a,b,c);
        else upd(1,b,c),upd(a,e,c); //add all up to m operations
    }
    vector<ll> can,cannot;
    for (auto u:pple){
        ll tot=0;
        for (auto x:adj[u]){
            tot+=query(x);
        }
        if (tot>=arr[u]) can.emplace_back(u);
        else cannot.emplace_back(u);
    }
    curr=m+1;
    q.emplace(l,m,can);
    q.emplace(m+1,r,cannot);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>e;
    vector<ll> pple;
    for (int i=1;i<=e;i++){
        cin>>ele;
        adj[ele].emplace_back(i);
    }
    for (int i=1;i<=n;i++){
        cin>>arr[i];
        pple.emplace_back(i);
    }
    cin>>op;
    for (int i=1;i<=op;i++){
        cin>>a>>b>>c;
        v.emplace_back(a,b,c);
    }
    v.emplace_back(1,e,inf);
    q.emplace(0,op,pple);
    while (q.size()){
        tie(a,b,pple) = q.front();
        q.pop();
        solve(a,b,pple);
    }
    for (int i=1;i<=n;i++){
        if (ans[i]==op) cout<<"NIE"<<endl;
        else cout<<ans[i]+1<<endl;
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 81 ms 13076 KB Output is correct
2 Correct 197 ms 14356 KB Output is correct
3 Correct 114 ms 13828 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 13532 KB Output is correct
2 Correct 155 ms 13504 KB Output is correct
3 Correct 186 ms 14064 KB Output is correct
4 Correct 46 ms 11540 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 121 ms 13272 KB Output is correct
2 Correct 177 ms 14304 KB Output is correct
3 Correct 114 ms 12332 KB Output is correct
4 Correct 120 ms 14040 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 12856 KB Output is correct
2 Correct 164 ms 13548 KB Output is correct
3 Correct 84 ms 13028 KB Output is correct
4 Correct 172 ms 14632 KB Output is correct

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

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