Submission #1086097

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086097		phong	Financial Report (JOI21_financial)	C++17	53 / 100	396 ms	36244 KiB

Main

#include<bits/stdc++.h>
#define ll long long
const int nmax = 3e5 + 5, N = 1e6;
const ll oo = 1e9 + 5, base = 311;
const int lg = 62, tx = 26;
const ll mod = 1e9 + 7;
#define pii pair<ll, ll>
#define fi first
#define se second
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;



int n, D;
int a[nmax];
namespace sub1{
    int f[nmax];

    void sol(){
        int ans = 0;
        for(int i = 1; i <= n; ++i) f[i] = 1;
        for(int i = 1; i <= n; ++i){
            int last = i;
            for(int j = i; j >= 1; --j){
                if(last - j > D) break;
                if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
                if(a[i] >= a[j]) last = j;
            }
            ans = max(ans, f[i]);
        }
        cout << ans;
    }
}
namespace sub2{
    int d[nmax];
    struct SG1{
        int tree[nmax << 2];
        void update(int id, int l, int r, int u, int val){
            if(l > u || r < u) return;
            if(l == r){
                tree[id] = val;
                return;
            }
            int mid = r + l >> 1;
            update(id << 1, l, mid, u, val);
            update(id << 1 | 1, mid + 1, r, u, val);
            tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
        }
        int get(int id, int l, int r, int u, int v){
            if(u > v) return 0;
            if(l >= u && r <= v) return tree[id];
            int mid = r + l >> 1;
            if(mid < u) return get(id << 1 | 1, mid + 1, r, u, v);
            if(mid + 1 > v) return get(id << 1, l, mid, u, v);
            return max(get(id << 1 | 1, mid + 1, r, u, v),get(id << 1, l, mid, u, v));
        }
    }one;


    set<int> mt;
    pii b[nmax];
    int rev[nmax], f[nmax];
    int r[nmax], mi[nmax];
    int get(int u){
        return r[u] ? r[u] = get(r[u]) : u;
    }
    void Union(int u, int v){
        u = get(u);v = get(v);
        if(u != v){
            r[u] = v;
            mi[v] = min(mi[v], mi[u]);
        }
    }
    void sol(){
        for(int i = 1; i <= n; ++i){
            b[i] = {a[i], i};
            mi[i] = i;
        }
        int ans = 1;
        sort(b + 1, b + 1 + n, [](pii a, pii b){
            if(a.fi == b.fi) return a.se > b.se;
            return a.fi < b.fi;
             });
        int pos = 1;
        mt.insert(-oo);
        mt.insert(oo);
        for(int i = 1; i <= n; ++i){
            while(pos <= n && b[pos].fi <= b[i].fi){
                auto it = mt.lower_bound(b[pos].se);
                int tx = *it;
                if(abs(tx - b[pos].se) <= D) Union(tx, b[pos].se);
                --it;
                tx = *it;
                if(abs(tx - b[pos].se) <= D) Union(tx, b[pos].se);
                mt.insert(b[pos].se);
                ++pos;
            }
            auto it = mt.lower_bound(b[i].fi);
            --it;
            int tx = *it;
            int p = b[i].se;
            if(abs(tx - b[i].se) <= D) p = mi[get(tx)];
            int val = one.get(1, 1, n, p - D, b[i].se) + 1;
            one.update(1, 1, n, b[i].se, val);
            f[b[i].se] = val;
        }
        cout << one.tree[1];
    }
}
vector<int> nen;
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> D;
    for(int i = 1; i <= n; ++i) cin >> a[i], nen.push_back(a[i]);
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for(int i = 1; i <= n; ++i) a[i] = lower_bound(nen.begin(), nen.end(), a[i]) - nen.begin() + 1;
    if(n <= 7000) sub1::sol();
    else sub2::sol();


}
/*
3 4
3 1
1 2
2 3
1 3



*/

Compilation message (stderr)

Main.cpp: In member function 'void sub2::SG1::update(int, int, int, int, int)':
Main.cpp:45:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |             int mid = r + l >> 1;
      |                       ~~^~~
Main.cpp: In member function 'int sub2::SG1::get(int, int, int, int, int)':
Main.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |             int mid = r + l >> 1;
      |                       ~~^~~
Main.cpp: In function 'void sub2::sol()':
Main.cpp:80:13: warning: unused variable 'ans' [-Wunused-variable]
   80 |         int ans = 1;
      |             ^~~
Main.cpp: At global scope:
Main.cpp:112:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  112 | main(){
      | ^~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 0 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35