oj.uz

Submission #751548

# Submission time Handle Problem Language Result Execution time Memory
751548 2023-05-31T18:01:07 Z mhy908 Tortoise (CEOI21_tortoise) C++14
0 / 100
 1 ms 340 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Incorrect 1 ms 304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Incorrect 1 ms 304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Incorrect 1 ms 304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Incorrect 1 ms 304 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 1 ms 304 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 0 ms 304 KB Output is correct
16 Incorrect 1 ms 304 KB Output isn't correct
17 Halted 0 ms 0 KB -