oj.uz

Submission #1096456

# Submission time Handle Problem Language Result Execution time Memory
1096456 2024-10-04T13:21:52 Z quangnamoiracvl_ralaidecu Global Warming (CEOI18_glo) C++14
42 / 100
 277 ms 16464 KB 
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5, mod = 1e9;
 
int n,k,a[N],st[4*N], dp[N], dpv[N],l[N], b[N]; map<int,int> s;
 
void update(int id, int l, int r, int pos, int val){
    if(pos < l || pos > r) return;
    if(l == r){
       st[id] = val ;
       return;
    }
    int mid = (l+r)/2;
    update(id*2, l, mid, pos, val);
    update(id*2+1, mid+1, r, pos, val);
    st[id] = max(st[id*2] , st[id*2+1]) ;
}
 
int get(int id, int l, int r, int u, int v){
    if(r < u || l > v) return 0;
    if(l >= u && r <= v) return st[id];
 
    int mid = (l+r)/2;
    return max(get(id*2, l, mid, u, v) , get(id*2+1, mid+1, r, u, v)) ;
}
 
signed main()   
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);  bool cc = true; 
    cin >> n >> k; for ( int i = 1; i <= n; i++ ) 
      {
        cin >> a[i]; 
        s[a[i]] = 1;
      } if ( !k ) cc = false;
      s[k]++;
    int d = 0; 
    for ( auto v : s ) {
        d++;
        s[v.first] = d;
    }
    k = s[k];
    for ( int i = 1; i <= n; i++ ) {
        a[i] = s[a[i]];
        // yêu thảo nguyên vl
    }
    int ans = -1;
    for ( int i = 1; i <= n; i++ ) {
        dp[i] = get(1,1,d,1,a[i] - 1) + 1;
        ans = max( ans, dp[i]);
        update(1,1,d,a[i],dp[i]);
    }
    if ( !cc ) {
        cout << ans; 
        return 0;
    }
   // for ( int i = 1; i <= n; i++ ) cout << dp[i] << " "; cout << endl;
    for ( int i = 1; i <= 4 * N; i++ ) st[i] = 0;
    for ( int i = n; i >= 1; i-- )
        {
            dpv[i] = get( 1,1,n,a[i] + 1, n) + 1;
            ans = max( ans, dp[i] + get( 1, 1, n, a[i] - k + 1, n ) );
            update( 1, 1, n, a[i] , dpv[i] );
            
        }
       // for ( int i = 1; i <= n; i++ ) cout << dpv[i] << " "; cout << endl;
    cout << ans;
}

Compilation message

glo.cpp: In function 'int main()':
glo.cpp:58:46: warning: iteration 800019 invokes undefined behavior [-Waggressive-loop-optimizations]
   58 |     for ( int i = 1; i <= 4 * N; i++ ) st[i] = 0;
      |                                        ~~~~~~^~~
glo.cpp:58:24: note: within this loop
   58 |     for ( int i = 1; i <= 4 * N; i++ ) st[i] = 0;
      |                      ~~^~~~~~~~
glo.cpp:58:46: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [3200080, 3200083] is out of the bounds [0, 3200080] of object 'st' with type 'int [800020]' [-Warray-bounds]
   58 |     for ( int i = 1; i <= 4 * N; i++ ) st[i] = 0;
      |                                        ~~~~~~^~~
glo.cpp:5:14: note: 'st' declared here
    5 | int n,k,a[N],st[4*N], dp[N], dpv[N],l[N], b[N]; map<int,int> s;
      |              ^~
glo.cpp:58:46: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [3200080, 3200083] is out of the bounds [0, 3200080] of object 'st' with type 'int [800020]' [-Warray-bounds]
   58 |     for ( int i = 1; i <= 4 * N; i++ ) st[i] = 0;
      |                                        ~~~~~~^~~
glo.cpp:5:14: note: 'st' declared here
    5 | int n,k,a[N],st[4*N], dp[N], dpv[N],l[N], b[N]; map<int,int> s;
      |              ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3528 KB Output is correct
11 Correct 2 ms 3416 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3528 KB Output is correct
11 Correct 2 ms 3416 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 3 ms 3420 KB Output is correct
15 Correct 2 ms 3416 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3536 KB Output is correct
18 Correct 2 ms 3416 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3528 KB Output is correct
11 Correct 2 ms 3416 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 3 ms 3420 KB Output is correct
15 Correct 2 ms 3416 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3536 KB Output is correct
18 Correct 2 ms 3416 KB Output is correct
19 Correct 3 ms 3676 KB Output is correct
20 Incorrect 2 ms 3540 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 244 ms 13904 KB Output is correct
2 Correct 234 ms 15152 KB Output is correct
3 Correct 235 ms 15180 KB Output is correct
4 Correct 232 ms 15036 KB Output is correct
5 Correct 101 ms 8692 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6376 KB Output is correct
2 Correct 70 ms 6484 KB Output is correct
3 Correct 64 ms 6428 KB Output is correct
4 Correct 33 ms 5312 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 34 ms 5252 KB Output is correct
7 Incorrect 67 ms 6480 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 9500 KB Output is correct
2 Correct 123 ms 9296 KB Output is correct
3 Correct 277 ms 16020 KB Output is correct
4 Correct 157 ms 11600 KB Output is correct
5 Correct 77 ms 9972 KB Output is correct
6 Correct 155 ms 15700 KB Output is correct
7 Correct 145 ms 16464 KB Output is correct
8 Correct 90 ms 10288 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3420 KB Output is correct
2 Correct 2 ms 3420 KB Output is correct
3 Correct 2 ms 3420 KB Output is correct
4 Correct 2 ms 3420 KB Output is correct
5 Correct 2 ms 3420 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 2 ms 3420 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 3420 KB Output is correct
10 Correct 1 ms 3528 KB Output is correct
11 Correct 2 ms 3416 KB Output is correct
12 Correct 2 ms 3420 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 3 ms 3420 KB Output is correct
15 Correct 2 ms 3416 KB Output is correct
16 Correct 1 ms 3420 KB Output is correct
17 Correct 2 ms 3536 KB Output is correct
18 Correct 2 ms 3416 KB Output is correct
19 Correct 3 ms 3676 KB Output is correct
20 Incorrect 2 ms 3540 KB Output isn't correct
21 Halted 0 ms 0 KB -