oj.uz

Submission #589653

# Submission time Handle Problem Language Result Execution time Memory
589653 2022-07-05T05:15:18 Z 조영욱(#8409) Gorgeous Pill (FXCUP3_gorgeous) C++14
100 / 100
 460 ms 59464 KB 
#include <bits/stdc++.h>
using namespace std;

typedef pair<long long,long long> P;
vector<P> vec;

bool comp(P a,P b) {
    if (a.first==b.first) {
        return a.second>b.second;
    }
    return a.first<b.first;
}

int n;
int c[300000];
int d[300000];
const int sz=524288;
const long long INF=1e15;

struct Seg {
    long long seg[sz*2];
    void init() {
        for(int i=1;i<sz*2;i++) {
            seg[i]=-INF;
        }
    }
    long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        if (r<nodel||l>noder) {
            return -INF;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    void update(int i,long long val) {
        i+=sz;
        seg[i]=max(seg[i],val);
        while (i>1) {
            i/=2;
            seg[i]=max(seg[i*2],seg[i*2+1]);
        }
    }
};

Seg seg1; //���������� �� ��
Seg seg2; //�������� �� ��

long long dp[1000000];

int main(void) {
    seg1.init();
    seg2.init();
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&c[i]);
    }
    for(int i=0;i<n;i++) {
        scanf("%d",&d[i]);
    }
    for(int i=0;i<n;i++) {
        vec.push_back(P(i,i));
    }
    vec.push_back(P(0,n-1));
    for(int i=0;i<n;i++) {
        if (i+c[i]-1<n) {
            vec.push_back(P(i,i+c[i]-1));
        }
        if (i-c[i]+1>=0) {
            vec.push_back(P(i-c[i]+1,i));
        }
    }
    sort(vec.begin(),vec.end(),comp);
    vec.erase(unique(vec.begin(),vec.end()),vec.end());
    vector<P> save;
    for(int i=0;i<vec.size();i++) {
        if (i!=0&&vec[i-1].first!=vec[i].first) {
            for(int j=0;j<save.size();j++) {
                seg2.update(save[j].first,save[j].second);
            }
            save.clear();
        }
        long long val=max(seg1.sum(vec[i].second+1,sz-1),seg2.sum(vec[i].second,sz-1));
        if (i==0) {
            val=0;
        }
        dp[i]=val;
        long long pl=0;
        if (c[vec[i].second]==vec[i].second-vec[i].first+1) {
            pl=d[vec[i].second];
        }
        seg1.update(vec[i].second,dp[i]+pl);
        pl=0;
        if (c[vec[i].first]==vec[i].second-vec[i].first+1) {
            pl=d[vec[i].first];
        }
        save.push_back(P(vec[i].second,dp[i]+pl));
    }
    for(int i=0;i<vec.size();i++) {
        if (vec[i].first==vec[i].second) {
            //printf("%d %d\n",vec[i].first,vec[i].second);
            printf("%lld ",dp[i]+(c[vec[i].first]==1?d[vec[i].first]:0));
        }
    }
}

Compilation message

gorgeous.cpp: In function 'int main()':
gorgeous.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0;i<vec.size();i++) {
      |                 ~^~~~~~~~~~~
gorgeous.cpp:79:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j=0;j<save.size();j++) {
      |                         ~^~~~~~~~~~~~
gorgeous.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0;i<vec.size();i++) {
      |                 ~^~~~~~~~~~~
gorgeous.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
gorgeous.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d",&c[i]);
      |         ~~~~~^~~~~~~~~~~~
gorgeous.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf("%d",&d[i]);
      |         ~~~~~^~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 7 ms 16636 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 7 ms 16636 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 9 ms 16836 KB Output is correct
10 Correct 10 ms 16736 KB Output is correct
11 Correct 9 ms 16724 KB Output is correct
12 Correct 9 ms 16724 KB Output is correct
13 Correct 8 ms 16744 KB Output is correct
14 Correct 8 ms 16868 KB Output is correct
15 Correct 9 ms 16852 KB Output is correct

Subtask #3
49.0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16724 KB Output is correct
2 Correct 7 ms 16724 KB Output is correct
3 Correct 9 ms 16724 KB Output is correct
4 Correct 7 ms 16724 KB Output is correct
5 Correct 7 ms 16636 KB Output is correct
6 Correct 7 ms 16724 KB Output is correct
7 Correct 9 ms 16724 KB Output is correct
8 Correct 8 ms 16732 KB Output is correct
9 Correct 9 ms 16836 KB Output is correct
10 Correct 10 ms 16736 KB Output is correct
11 Correct 9 ms 16724 KB Output is correct
12 Correct 9 ms 16724 KB Output is correct
13 Correct 8 ms 16744 KB Output is correct
14 Correct 8 ms 16868 KB Output is correct
15 Correct 9 ms 16852 KB Output is correct
16 Correct 13 ms 17284 KB Output is correct
17 Correct 36 ms 18724 KB Output is correct
18 Correct 147 ms 24724 KB Output is correct
19 Correct 163 ms 27052 KB Output is correct
20 Correct 437 ms 40820 KB Output is correct
21 Correct 460 ms 42020 KB Output is correct
22 Correct 452 ms 42096 KB Output is correct
23 Correct 449 ms 41912 KB Output is correct
24 Correct 432 ms 42036 KB Output is correct
25 Correct 404 ms 59464 KB Output is correct