oj.uz

Submission #968098

# Submission time Handle Problem Language Result Execution time Memory
968098 2024-04-23T07:40:22 Z LittleOrange Real Mountains (CCO23_day1problem2) C++17
13 / 25
 5000 ms 59460 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e6+3;
const ll big = 1e10;
struct l{
    ll x;
    l(const ll &x):x((x+mod)%mod){}
    l(const int &x):x((x+mod)%mod){}
    l operator+(const l& o) const{
        return l(x+o.x);
    }
    l operator-(const l& o) const{
        return l(x-o.x);
    }
    l operator*(const l& o) const{
        return l(x*o.x);
    }
    l operator+(const ll& o) const{
        return l(x+o);
    }
    l operator-(const ll& o) const{
        return l(x-o);
    }
    l operator*(const ll& o) const{
        return l(x*o);
    }
    l operator+(const int& o) const{
        return l(x+o);
    }
    l operator-(const int& o) const{
        return l(x-o);
    }
    l operator*(const int& o) const{
        return l(x*o);
    }
    operator ll() const{
        return x;
    }
};
const l rev2 = l(500002);
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n);
    ll mxa = 0;
    for(ll &i : a) cin >> i,mxa = max(mxa,i);
    vector<ll> b = a;
    //for(ll i = 1;i<=mxa;i++) b.push_back(i);
    sort(b.begin(),b.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    l ans = 0;
    vector<ll> li = a;
    vector<ll> ri = a;
    for(ll i = 1;i<n;i++) li[i] = max(li[i],li[i-1]);
    for(ll i = n-2;i>=0;i--) ri[i] = max(ri[i],ri[i+1]);
    for(ll j = 0;j<b.size()-1;j++){
        l de = b[j+1]-b[j];
        vector<ll> v;
        for(ll i = 0;i<n;i++){
            if (a[i]<=b[j]&&li[i]>b[j]&&ri[i]>b[j]) v.push_back(i);
        }
        if(v.empty()) continue;
        //cout << b[j] << ":";
        //for(ll i : v) cout << " " << i;
        //cout << "\n";
        vector<ll> L(n,big),R(n,big);
        for(ll i = 0;i<n;i++) if(a[i]>b[j]) L[i] = R[i] = a[i];
        for(ll i = 1;i<n;i++) L[i] = min(L[i],L[i-1]);
        for(ll i = n-2;i>=0;i--) R[i] = min(R[i],R[i+1]);
        //for(ll i = 0;i<n;i++) cout << L[i] << " \n"[i+1==n];
        //for(ll i = 0;i<n;i++) cout << R[i] << " \n"[i+1==n];
        if (v.size()==1){
            ll i = v[0];
            ans = ans+l(L[i]+R[i]+b[j])*de+de*(de-1)*rev2;
        }else{
            l base = (L[v.front()]+R[v.back()]+min(R[v.front()],L[v.back()]));
            l cnt0 = (ll)v.size();
            l cnt = (cnt0*2-3);
            //cout << base << " " << cnt << " " << de << "\n";
            ans = ans+base*de+cnt*(b[j]*de+de*(de+1)*rev2)+cnt0*(b[j]*de+de*(de-1)*rev2);
        }
    }
    cout << ans << "\n";
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:58:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(ll j = 0;j<b.size()-1;j++){
      |                  ~^~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 350 ms 752 KB Output is correct
36 Correct 349 ms 1040 KB Output is correct
37 Correct 348 ms 788 KB Output is correct
38 Correct 344 ms 876 KB Output is correct
39 Correct 340 ms 784 KB Output is correct
40 Correct 2 ms 772 KB Output is correct
41 Correct 2 ms 776 KB Output is correct
42 Correct 2 ms 776 KB Output is correct
43 Correct 297 ms 1004 KB Output is correct
44 Correct 273 ms 792 KB Output is correct
45 Correct 282 ms 784 KB Output is correct
46 Correct 318 ms 796 KB Output is correct
47 Correct 295 ms 784 KB Output is correct
48 Correct 300 ms 928 KB Output is correct

Subtask #4
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 350 ms 752 KB Output is correct
36 Correct 349 ms 1040 KB Output is correct
37 Correct 348 ms 788 KB Output is correct
38 Correct 344 ms 876 KB Output is correct
39 Correct 340 ms 784 KB Output is correct
40 Correct 2 ms 772 KB Output is correct
41 Correct 2 ms 776 KB Output is correct
42 Correct 2 ms 776 KB Output is correct
43 Correct 297 ms 1004 KB Output is correct
44 Correct 273 ms 792 KB Output is correct
45 Correct 282 ms 784 KB Output is correct
46 Correct 318 ms 796 KB Output is correct
47 Correct 295 ms 784 KB Output is correct
48 Correct 300 ms 928 KB Output is correct
49 Incorrect 341 ms 848 KB Output isn't correct
50 Halted 0 ms 0 KB -

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1945 ms 55564 KB Output is correct
36 Correct 1899 ms 55580 KB Output is correct
37 Correct 1919 ms 55780 KB Output is correct
38 Correct 1936 ms 56056 KB Output is correct
39 Correct 1870 ms 55844 KB Output is correct
40 Correct 1 ms 344 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 261 ms 55500 KB Output is correct
43 Correct 258 ms 59460 KB Output is correct
44 Correct 261 ms 55856 KB Output is correct
45 Correct 1462 ms 56076 KB Output is correct
46 Correct 1426 ms 55600 KB Output is correct
47 Correct 1479 ms 55996 KB Output is correct
48 Correct 1633 ms 55804 KB Output is correct
49 Correct 1602 ms 55608 KB Output is correct
50 Correct 1660 ms 55944 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 350 ms 752 KB Output is correct
36 Correct 349 ms 1040 KB Output is correct
37 Correct 348 ms 788 KB Output is correct
38 Correct 344 ms 876 KB Output is correct
39 Correct 340 ms 784 KB Output is correct
40 Correct 2 ms 772 KB Output is correct
41 Correct 2 ms 776 KB Output is correct
42 Correct 2 ms 776 KB Output is correct
43 Correct 297 ms 1004 KB Output is correct
44 Correct 273 ms 792 KB Output is correct
45 Correct 282 ms 784 KB Output is correct
46 Correct 318 ms 796 KB Output is correct
47 Correct 295 ms 784 KB Output is correct
48 Correct 300 ms 928 KB Output is correct
49 Correct 1945 ms 55564 KB Output is correct
50 Correct 1899 ms 55580 KB Output is correct
51 Correct 1919 ms 55780 KB Output is correct
52 Correct 1936 ms 56056 KB Output is correct
53 Correct 1870 ms 55844 KB Output is correct
54 Correct 1 ms 344 KB Output is correct
55 Correct 1 ms 348 KB Output is correct
56 Correct 261 ms 55500 KB Output is correct
57 Correct 258 ms 59460 KB Output is correct
58 Correct 261 ms 55856 KB Output is correct
59 Correct 1462 ms 56076 KB Output is correct
60 Correct 1426 ms 55600 KB Output is correct
61 Correct 1479 ms 55996 KB Output is correct
62 Correct 1633 ms 55804 KB Output is correct
63 Correct 1602 ms 55608 KB Output is correct
64 Correct 1660 ms 55944 KB Output is correct
65 Execution timed out 5003 ms 51972 KB Time limit exceeded
66 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 6 ms 776 KB Output is correct
5 Correct 1 ms 600 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 776 KB Output is correct
13 Correct 8 ms 776 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 9 ms 772 KB Output is correct
17 Correct 8 ms 764 KB Output is correct
18 Correct 8 ms 772 KB Output is correct
19 Correct 8 ms 764 KB Output is correct
20 Correct 2 ms 776 KB Output is correct
21 Correct 2 ms 772 KB Output is correct
22 Correct 2 ms 776 KB Output is correct
23 Correct 6 ms 756 KB Output is correct
24 Correct 6 ms 776 KB Output is correct
25 Correct 6 ms 764 KB Output is correct
26 Correct 7 ms 764 KB Output is correct
27 Correct 7 ms 764 KB Output is correct
28 Correct 7 ms 760 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 350 ms 752 KB Output is correct
36 Correct 349 ms 1040 KB Output is correct
37 Correct 348 ms 788 KB Output is correct
38 Correct 344 ms 876 KB Output is correct
39 Correct 340 ms 784 KB Output is correct
40 Correct 2 ms 772 KB Output is correct
41 Correct 2 ms 776 KB Output is correct
42 Correct 2 ms 776 KB Output is correct
43 Correct 297 ms 1004 KB Output is correct
44 Correct 273 ms 792 KB Output is correct
45 Correct 282 ms 784 KB Output is correct
46 Correct 318 ms 796 KB Output is correct
47 Correct 295 ms 784 KB Output is correct
48 Correct 300 ms 928 KB Output is correct
49 Incorrect 341 ms 848 KB Output isn't correct
50 Halted 0 ms 0 KB -