oj.uz

Submission #999168

# Submission time Handle Problem Language Result Execution time Memory
999168 2024-06-15T07:46:02 Z vjudge1 LIS (INOI20_lis) C++17
20 / 100
 4000 ms 1980 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 75 ms 572 KB Output is correct
4 Correct 141 ms 536 KB Output is correct
5 Correct 74 ms 344 KB Output is correct
6 Correct 140 ms 548 KB Output is correct
7 Correct 91 ms 596 KB Output is correct
8 Correct 92 ms 572 KB Output is correct
9 Correct 104 ms 348 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 100 ms 560 KB Output is correct
12 Correct 107 ms 344 KB Output is correct
13 Correct 153 ms 532 KB Output is correct
14 Correct 150 ms 544 KB Output is correct
15 Correct 113 ms 348 KB Output is correct
16 Correct 148 ms 348 KB Output is correct
17 Correct 168 ms 556 KB Output is correct
18 Correct 143 ms 348 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 75 ms 572 KB Output is correct
4 Correct 141 ms 536 KB Output is correct
5 Correct 74 ms 344 KB Output is correct
6 Correct 140 ms 548 KB Output is correct
7 Correct 91 ms 596 KB Output is correct
8 Correct 92 ms 572 KB Output is correct
9 Correct 104 ms 348 KB Output is correct
10 Correct 86 ms 344 KB Output is correct
11 Correct 100 ms 560 KB Output is correct
12 Correct 107 ms 344 KB Output is correct
13 Correct 153 ms 532 KB Output is correct
14 Correct 150 ms 544 KB Output is correct
15 Correct 113 ms 348 KB Output is correct
16 Correct 148 ms 348 KB Output is correct
17 Correct 168 ms 556 KB Output is correct
18 Correct 143 ms 348 KB Output is correct
19 Execution timed out 4073 ms 1980 KB Time limit exceeded
20 Halted 0 ms 0 KB -