oj.uz

Submission #484073

# Submission time Handle Problem Language Result Execution time Memory
484073 2021-11-02T05:13:00 Z kaxzert Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 0 ms 204 KB 
/**
      00  00      11      00  00  111111  00000  111111  000000
      00 00      1111      0000      11   00     11  11  000000
      0000      11  11      00      11    00000  111111    00
      00 00    11111111    0000    11     00     11 11     00
      00  00  11      11  00  00  111111  00000  11  11    00
**/

#include<bits/stdc++.h>

using namespace std;

#define fto(i, a, b) for(int i = a; i <= b; ++i)
#define fdto(i, a, b) for(int i = a; i >= b; --i)
#define bugarr(a, i, j) cout << #a << "{" << i << "..." << j << "}:"; fto(k, i, j-1) cout << a[k] << ", "; cout << a[j] << endl;
#define ll long long
#define db double
#define ldb long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define vt vector
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define trav(i, a) for(auto &i : a)
#define sz(a) (int)a.size()
#define pi(a, b) pair<a, b>
#define fast ios::sync_with_stdio(false); cin.tie(0)

void setIO(string s) {
    if (sz(s) != 0) {
        freopen((s+".inp").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

void setIOusaco(string s) {
    if (sz(s) != 0) {
        freopen((s+".in").c_str(),"r",stdin);
        freopen((s+".out").c_str(),"w",stdout);
    }
}

template<typename T, typename V>
bool ckmin(T &a, V b) {return (b < a)? a = b, true : false;}
template<typename T, typename V>
bool ckmax(T &a, V b) {return (b > a)? a = b, true : false;}

int main() {
    #ifndef TAP 
    //setIO("triusis2019");
    //setIOusaco("triusis2019");
    #endif

    fast;
    int n;
    ll m;
    cin >> n >> m;
    vt<ll> h(n+2);
    fto(i, 1, n) {
    	cin >> h[i];
    }
    h[n+1] = 0;

    vt<pi(ll, ll) > lis;
    lis.eb(0, 0);

    auto tk = [&](ll x, ll pos) -> int{
        int left = 0, right = sz(lis)-1;
        int res = 1e9;
        while(left <= right) {
            int mid = (left+right)/2;
            if (lis[mid].ff+(pos-lis[mid].ss)*m < x) {
                res = mid;
                right = mid-1;
            } else left = mid+1;
        }
        return res;
    };

    fto(i, 1, n) {
        int sth = tk(h[i], i);
        if (sth == 0) h[i] = i*m;
        if (sth != 1e9) {
            int temp = sz(lis)-1;
            fdto(i, temp, sth) lis.pop_back();
        }
        lis.eb(h[i], i);
    }

    cout << n-sz(lis)+1 << '\n';

    return 0;
}

Compilation message

triusis.cpp: In function 'void setIO(std::string)':
triusis.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen((s+".inp").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp: In function 'void setIOusaco(std::string)':
triusis.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen((s+".in").c_str(),"r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen((s+".out").c_str(),"w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Incorrect 0 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -