oj.uz

Submission #589758

# Submission time Handle Problem Language Result Execution time Memory
589758 2022-07-05T08:40:20 Z 반딧불(#8407) Gorgeous Pill (FXCUP3_gorgeous) C++14
100 / 100
 270 ms 44156 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].begin(), under[i].end());
        sort(update[i].begin(), update[i].end());
        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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 7 ms 14380 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14404 KB Output is correct
14 Correct 8 ms 14488 KB Output is correct
15 Correct 8 ms 14416 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14292 KB Output is correct
2 Correct 8 ms 14292 KB Output is correct
3 Correct 8 ms 14292 KB Output is correct
4 Correct 8 ms 14292 KB Output is correct
5 Correct 8 ms 14404 KB Output is correct
6 Correct 8 ms 14404 KB Output is correct
7 Correct 9 ms 14404 KB Output is correct
8 Correct 7 ms 14380 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 8 ms 14420 KB Output is correct
11 Correct 8 ms 14420 KB Output is correct
12 Correct 8 ms 14420 KB Output is correct
13 Correct 9 ms 14404 KB Output is correct
14 Correct 8 ms 14488 KB Output is correct
15 Correct 8 ms 14416 KB Output is correct
16 Correct 10 ms 14676 KB Output is correct
17 Correct 23 ms 16204 KB Output is correct
18 Correct 73 ms 21700 KB Output is correct
19 Correct 92 ms 24004 KB Output is correct
20 Correct 270 ms 36788 KB Output is correct
21 Correct 228 ms 37904 KB Output is correct
22 Correct 239 ms 37920 KB Output is correct
23 Correct 241 ms 37812 KB Output is correct
24 Correct 244 ms 37888 KB Output is correct
25 Correct 134 ms 44156 KB Output is correct