Submission #782851

#TimeUsernameProblemLanguageResultExecution timeMemory
782851RushBLIS (INOI20_lis)C++17
0 / 100
22 ms16468 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i < (b); i++) const int64_t INF = 1ll << 60; const int N = 1e6 + 6; const int SQ = 1000 + 5; int n, x[N], p[N], a[N], S, q, ans[N]; vector<int> V[SQ]; pair<int, int> bit[N]; void addf(int r, pair<int, int> m) { for (; r < N; r += r & -r) bit[r] = max(bit[r], m); } pair<int, int> getf(int r) { pair<int, int> x = {0, INF}; for (; r; r -= r & -r) x = max(x, bit[r]); return x; } void rebuild() { vector<int> x; FOR(i, 0, SQ) { for (auto u: V[i]) x.push_back(u); V[i].clear(); } for (int i = 0; i < x.size(); i++) V[i / SQ].push_back(x[i]); } void add(vector<int> &v, int pos, int x) { vector<int> t; for (int i = 0; i < pos; i++) t.push_back(v[i]); t.push_back(x); for (int i = pos; i < v.size(); i++) t.push_back(v[i]); v = t; } void seq() { FOR(i, 0, q) { if ((i + 1) % SQ == 0) rebuild(); int cur = p[i] - 1; FOR(j, 0, SQ) { if (cur > V[j].size()) cur -= V[j].size(); else { add(V[j], cur, i); } } } int ptr = 0; FOR(i, 0, SQ) for (auto u: V[i]) a[ptr++] = u; } void solve() { int cnt = 0; while (true) { assert(++cnt <= 2000); pair<int, int> lis = {0, INF}; fill(bit, bit + N, lis); FOR(i, 0, q) { auto p = getf(x[a[i]] - 1); p.first++; p.second = min(p.second, -a[i]); lis = max(lis, p); addf(x[a[i]], p); } for (int i = q - 1; i >= -lis.second; i--) ans[i] = lis.first; if (lis.second == 0) return; vector<int> v; FOR(i, 0, q) if (a[i] < -lis.second) v.push_back(a[i]); q = v.size(); copy(v.begin(), v.end(), a); } } signed main() { ios::sync_with_stdio(0), cin.tie(0); cin >> q; int tq = q; vector<int> X; FOR(i, 0, q) { cin >> p[i] >> x[i]; X.push_back(x[i]); } sort(X.begin(), X.end()); X.resize(unique(X.begin(), X.end()) - X.begin()); FOR(i, 0, q) x[i] = lower_bound(X.begin(), X.end(), x[i]) - X.begin(); seq(); solve(); FOR(i, 0, tq) cout << ans[i] << '\n'; } //12:54:46

Compilation message (stderr)

Main.cpp: In function 'void rebuild()':
Main.cpp:27:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i = 0; i < x.size(); i++)
      |                         ~~^~~~~~~~~~
Main.cpp: In function 'void add(std::vector<int>&, int, int)':
Main.cpp:34:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for (int i = pos; i < v.size(); i++) t.push_back(v[i]);
      |                           ~~^~~~~~~~~~
Main.cpp: In function 'void seq()':
Main.cpp:43:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                         if (cur > V[j].size()) cur -= V[j].size();
      |                             ~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...