Submission #999168

#	Time	Username	Problem	Language	Result	Execution time	Memory
999168		vjudge1	LIS (INOI20_lis)	C++17	20 / 100	4073 ms	1980 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"

using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct SegTree
{
    ll n;
    vector<ll> st;
    SegTree(ll sz = 0, bool input = false)
    {
        n = sz;
        st.resize((n + 1) << 1, 0);
    }
    void modify(ll p, ll val)
    {
        for (st[p += n - 1] = val; p > 1; p >>= 1)
            st[p >> 1] = max(st[p], st[p ^ 1]);
    }
    ll query(ll l, ll r)
    {
        ll ans = 0;
        for (l += n - 1, r += n; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1)
                ans = max(ans, st[l++]);
            if (r & 1)
                ans = max(ans, st[--r]);
        }
        return ans;
    }
};
void solve()
{
   ll q;
   cin >> q;
   vector<ll> v, dp;
   map<ll, ll> mp;
   while (q--)
   {
       ll p, x;
       cin >> p >> x;
       p--;
       v.insert(v.begin() + p, x);
       dp.push_back(0);
       {
           mp.clear();
           for (ll i : v)
            mp[i] = 1;
            ll cur = 1;
            for (auto i : mp)
                mp[i.first] = cur++;
       }
       SegTree st(v.size());
       for (ll i = 0; i < v.size(); i++)
        dp[i] = st.query(1, mp[v[i]] - 1) + 1, st.modify(mp[v[i]], dp[i]);
        cout << *max_element(dp.begin(), dp.end()) << endl;
   }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:56:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |        for (ll i = 0; i < v.size(); i++)
      |                       ~~^~~~~~~~~~
Main.cpp:56:8: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   56 |        for (ll i = 0; i < v.size(); i++)
      |        ^~~
Main.cpp:58:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |         cout << *max_element(dp.begin(), dp.end()) << endl;
      |         ^~~~

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80