Submission #751548

#	Time	Username	Problem	Language	Result	Execution time	Memory
751548		mhy908	Tortoise (CEOI21_tortoise)	C++14	0 / 100	1 ms	340 KiB

tortoise

#include <bits/stdc++.h>
#define mp make_pair
#define eb emplace_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define svec(x) sort(all(x))
#define press(x) x.erase(unique(all(x)), x.end());
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
typedef pair<LL, LL> pll;
const int INF=1e9;
const LL LLINF=1e18;

struct FENWICK{
    int tree[500010];
    int sum(int i){
        int ans=0;
        for(; i; i-=(i&-i))ans+=tree[i];
        return ans;
    }
    void upd(int i, int num){
        for(; i<=500000; i+=(i&-i))tree[i]+=num;
    }
}fen;

int n, arr[500010];

int bf[500010], af[500010];
int tar[500010];

int rgt[500010];

LL ans;

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++)scanf("%d", &arr[i]);

    for(int i=1; i<=n; i++)ans+=max(0, arr[i]);

    bf[0]=-INF;
    af[n+1]=INF;
    for(int i=1; i<=n; i++){
        bf[i]=bf[i-1];
        if(arr[i]==-1)bf[i]=i;
    }
    for(int i=n; i>=1; i--){
        af[i]=af[i+1];
        if(arr[i]==-1)af[i]=i;
    }

    int prv=INF+1;
    for(int i=n; i>=1; i--){
        if(af[i]==prv||arr[i]<=0)continue;
        prv=af[i];
        arr[i]--;
        ans--;
        rgt[af[i]==INF?0:af[i]]=i;
    }

    vector<pii> vc;
    for(int i=1; i<=n; i++){
        int d=min(af[i]-i, i-bf[i]);
        if(arr[i]>0)vc.eb(d, i);
    }
    svec(vc);

    for(auto i:vc){
        while(arr[i.S]){
            int a=(af[i.S]==INF?0:af[i.S]);
            int nw=fen.sum(rgt[a]);
            int nw2=fen.sum(i.S);
            if(nw2<i.S&&nw+i.F*2<rgt[a]){
                fen.upd(i.S, i.F*2);
                ans--;
                arr[i.S]--;
            }
            else break;
        }
    }

    printf("%lld", ans);
}

Compilation message (stderr)

tortoise.cpp: In function 'int main()':
tortoise.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
tortoise.cpp:41:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     for(int i=1; i<=n; i++)scanf("%d", &arr[i]);
      |                            ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 25
• Subtask 5: 0 / 27