Submission #783003

#TimeUsernameProblemLanguageResultExecution timeMemory
783003RushBLIS (INOI20_lis)C++17
20 / 100
4056 ms6916 KiB
#include <bits/stdc++.h> using namespace std; #define FOR(i, a, b) for (int i = (a); i < (b); i++) using ar = array<int, 2>; const int INF = 1ll << 30; const int N = 1e6 + 6; const int SQ = 3000; const int SQQ = 2000 + 5; int n, x[N], p[N], S, q, ans[N], mx, X[N], tmp[N]; vector<int> V[N / SQ + 5]; ar M[SQQ], a[N], b[N]; void rebuild() { int ptr = 0; for (int i = 0; V[i].size(); i++) { for (auto u: V[i]) tmp[ptr++] = u; V[i].clear(); } mx = 0; FOR(i, 0, ptr) { V[i >> 11].push_back(tmp[i]); mx = max(mx, (int) V[i >> 11].size()); } } inline void add(vector<int> &v, int pos, int x) { if (pos == v.size()) { v.push_back(x); return; } v.insert(v.begin() + pos, x); mx = max(mx, (int) v.size()); } void seq() { FOR(i, 0, q) { if (mx >= (1 << 11)) rebuild(); int cur = p[i] - 1; for (int j = 0; j <= i; j++) { if (cur > V[j].size()) cur -= V[j].size(); else { add(V[j], cur, i); break; } } } int ptr = 0; for (int i = 0; V[i].size(); i++) for (auto u: V[i]) a[ptr][0] = u, a[ptr][1] = x[u], ptr++; } void solve() { while (true) { ar lis = {0, INF}; fill(M, M + SQQ, lis); FOR(i, 0, q) { ar p = *max_element(M, M + a[i][1]); p[0]++, p[1] = min(p[1], -a[i][0]); M[a[i][1]] = max(M[a[i][1]], p); } lis = *max_element(M, M + SQQ); for (int i = q - 1; i >= -lis[1]; i--) ans[i] = lis[0]; if (!lis[1]) return; int ptr = 0; FOR(i, 0, q) if (a[i][0] < -lis[1]) b[ptr++] = a[i]; q = ptr; copy(b, b + ptr, 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() + 1; } assert(X.size() <= SQQ); seq(); solve(); FOR(i, 0, tq) cout << ans[i] << '\n'; } //12:54:46

Compilation message (stderr)

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