oj.uz

Submission #589756

# Submission time Handle Problem Language Result Execution time Memory
589756 2022-07-05T08:39:28 Z 반딧불(#8407) Gorgeous Pill (FXCUP3_gorgeous) C++14
0 / 100
 8 ms 14292 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int n;
int c[300002];
ll d[300002];
vector<pair<int, ll> > under[300002];
vector<pair<int, ll> > update[300002];
map<int, ll> mp;
ll ans[300002];
ll sum;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &c[i]);
    for(int i=1; i<=n; i++) scanf("%lld", &d[i]);
    for(int i=1; i<=n; i++){
        if(c[i]==1) continue;
        if(i-c[i]+1 >= 1){ /// under: [l, i] -> [l, i-1]
            under[i-1].push_back(make_pair(i-c[i]+1, d[i]));
//            printf("Under %d -> %d %lld\n", i-1, i-c[i]+1, d[i]);
        }
        if(i+c[i]-1 <= n){
            update[i+c[i]-1].push_back(make_pair(i+1, d[i]));
//            printf("Update %d -> %d %lld\n", i+c[i]-1, i+1, d[i]);
        }
    }
    for(int i=n; i>=1; i--){
        sort(under[i].rbegin(), under[i].rend());
        sort(update[i].rbegin(), update[i].rend());
        while(!mp.empty() && mp.rbegin()->first > i){
            sum -= mp.rbegin()->second;
            mp.erase(prev(mp.end()));
        }
        for(pair<int, ll> p: under[i]){
            ll v = p.second;
            auto it = mp.upper_bound(p.first);
            while(it != mp.end()){
                ll tmp = min(v, it->second);
                v -= tmp, it->second -= tmp, sum -= tmp;
                if(!it->second){
                    mp.erase(it);
                    it = mp.upper_bound(p.first);
                }
                if(!v) break;
            }
            mp[p.first] += p.second;
            sum += p.second;
        }
        for(pair<int, ll> p: update[i]){
            ll v = p.second;
            auto it = mp.lower_bound(p.first);
            while(it != mp.end()){
                ll tmp = min(v, it->second);
                v -= tmp, it->second -= tmp, sum -= tmp;
                if(!it->second){
                    mp.erase(it);
                    it = mp.lower_bound(p.first);
                }
                if(!v) break;
            }
            mp[p.first] += p.second;
            sum += p.second;
        }
//        printf("%d: ", i);
//        for(auto x: mp) printf("(%d, %lld) ", x.first, x.second);
//        puts("");
        ans[i] = sum;
    }
    for(int i=1; i<=n; i++){
        if(c[i] == 1) ans[i] += d[i];
    }
    for(int i=1; i<=n; i++){
        printf("%lld ", ans[i]);
    }
}

Compilation message

gorgeous.cpp: In function 'int main()':
gorgeous.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
gorgeous.cpp:18:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     for(int i=1; i<=n; i++) scanf("%d", &c[i]);
      |                             ~~~~~^~~~~~~~~~~~~
gorgeous.cpp:19:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1; i<=n; i++) scanf("%lld", &d[i]);
      |                             ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Incorrect 7 ms 14292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Incorrect 7 ms 14292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Incorrect 7 ms 14292 KB Output isn't correct
4 Halted 0 ms 0 KB -