oj.uz

Submission #874955

# Submission time Handle Problem Language Result Execution time Memory
874955 2023-11-18T09:33:57 Z efedmrlr Financial Report (JOI21_financial) C++17
12 / 100
 307 ms 31660 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 1e5+5;
const int MOD = 1e9+7;
const int INF = 1e12;
const int M = 1e6+5;
const long double EPS = 0.00001;
 
int n,m,q,d;
vector<int> dp, b;
vector<array<int,2> > a;
struct SegTree {
    int sz;
    vector<int> data, lazy;
    SegTree(int sz) {
        this->sz = sz;
        data.assign(4*(sz + 2), 0);
        lazy.assign(4*(sz + 2), -1);

    }
    void push(int v) {
        if(lazy[v] == -1) return;
        data[v*2] = lazy[v];
        data[v*2+1] = lazy[v];
        lazy[v*2] = lazy[v];
        lazy[v*2+1] = lazy[v];
        lazy[v] = -1;
    }
    void update(int tl, int tr ,int v, int l, int r, int val) {
        if(tl >= l && tr <= r) {
            lazy[v] = val;
            data[v] = val;
            return;
        }
        if(tl > r || tr < l) {
            return;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        update(tl, tm, v*2, l, r, val);
        update(tm + 1, tr, v*2+1, l, r, val);
        data[v] = max(data[v*2], data[v*2+1]);
    }
    void update(int l ,int r, int val) {
        update(0, sz, 1, l, r, val);
    }
    int query(int tl, int tr, int v, int l, int r) {
        if(tl >= l && tr <= r) return data[v];
        if(tl > r || tr < l) {
            return 0;
        }
        push(v);
        int tm = (tl + tr) >> 1;
        return max(query(tl, tm, v*2, l, r) , query(tm + 1, tr, v*2+1, l, r));
    }
    int query(int l, int r) {
        return query(0, sz, 1, l, r);
    }
};

void compress() {
    sort(a.begin(), a.end());
    int last = 0;
    int cur = 0;
    for(int i = 0; i<n; i++) {
        if(a[i][0] == last) {
            a[i][0] = cur;
        }
        else {
            last = a[i][0];
            cur++;
            a[i][0] = cur;
        }
    }
    b.assign(n+1, 0);
    for(auto c : a) {
        b[c[1]] = c[0];
    }

}
signed main() {
    fastio();
    cin>>n>>d;
    a.resize(n);
    dp.assign(n + 1, 1);
    REP(i,n) {
        cin>>a[i][0];
        a[i][1] = i + 1;
    }

    compress();
    dp[n] = 1;
    SegTree st(n + 9);
    st.update(b[n], b[n], dp[n]);
    for(int i = n - 1; i>=1; i--) {
        dp[i] = st.query(b[i] + 1, n + 5) + 1;
        st.update(0, b[i] - 1, 0);
        st.update(b[i], b[i], dp[i]);
    }
    int ans = 0;
    for(int i = 1; i<=n; i++) {
        ans = max(ans , dp[i]);
    }
    cout<<ans<<"\n";

}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:8:26: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
    8 | #define REP(i,n) for(int (i) = 0; (i)<(n); (i)++)
      |                          ^
Main.cpp:98:5: note: in expansion of macro 'REP'
   98 |     REP(i,n) {
      |     ^~~

Subtask #1
0 / 14.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 20.0

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

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 28624 KB Output is correct
2 Correct 187 ms 28620 KB Output is correct
3 Correct 182 ms 28756 KB Output is correct
4 Correct 236 ms 31540 KB Output is correct
5 Correct 234 ms 31316 KB Output is correct
6 Correct 275 ms 31532 KB Output is correct
7 Correct 151 ms 31340 KB Output is correct
8 Correct 150 ms 31316 KB Output is correct
9 Correct 171 ms 31532 KB Output is correct
10 Correct 166 ms 31432 KB Output is correct
11 Correct 206 ms 31384 KB Output is correct
12 Correct 238 ms 31532 KB Output is correct
13 Correct 233 ms 31660 KB Output is correct
14 Correct 307 ms 31388 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 28476 KB Output is correct
2 Incorrect 193 ms 28480 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

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