QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#862132 | #9982. Staircase Museum | ucup-team4435# | WA | 7ms | 3712kb | C++20 | 3.0kb | 2025-01-18 22:04:41 | 2025-01-18 22:04:42 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
//#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const int INFi = 2e9;
const ll INF = 2e18;
void solve() {
int n; cin >> n;
vi l(n), r(n);
rep(i, n) cin >> l[i] >> r[i];
rep(i, n) r[i]++;
vpi up, down;
up.emplace_back(0, l[0]);
for(int i = 1; i < n; ++i) {
if (r[i] > r[i - 1]) {
up.emplace_back(i, r[i - 1]);
}
}
for(int i = 0; i < n; ++i) {
if (i + 1 == n || l[i + 1] > l[i]) {
down.emplace_back(i + 1, l[i]);
}
}
for(auto &[x, y] : up) {
x++;
}
int usz = up.size();
int dsz = down.size();
vi lu(usz), ru(usz);
int lptr = 0;
int rptr = 0;
rep(i, up.size()) {
while (rptr < down.size() && down[rptr].second <= up[i].second) rptr++;
while (lptr < down.size() && down[lptr].first < up[i].first) lptr++;
lu[i] = lptr;
ru[i] = rptr;
}
int ans = max(usz, dsz);
vi dp(usz);
int ls = -INFi, ms = -INFi;
int j = 0;
rep(i, up.size()) {
while (j < i && ru[j] <= lu[i]) {
ckmax(ls, dp[j] - ru[j]);
j++;
}
dp[i] = 1 + lu[i];
ckmax(dp[i], 1 + ls + lu[i]);
ckmax(dp[i], 1 + ms);
ckmax(ms, dp[i]);
ckmax(ans, dp[i] + dsz - ru[j]);
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
cin >> t;
rep(i, t) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3712kb
input:
4 3 1 2 1 3 1 3 3 1 2 2 3 3 3 3 1 1 1 3 3 3 4 1 2 2 3 3 4 4 5
output:
2 3 3 4
result:
ok 4 number(s): "2 3 3 4"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
1 1 1 1000000000
output:
1
result:
ok 1 number(s): "1"
Test #3:
score: -100
Wrong Answer
time: 7ms
memory: 3712kb
input:
9653 1 1 1 2 1 1 1 1 3 1 1 1 1 1 1 4 1 1 1 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1 1 6 1 1 1 1 1 1 1 1 1 1 1 1 6 1 2 1 2 1 2 1 2 1 2 2 2 6 1 1 1 1 1 1 1 1 1 1 1 2 6 1 2 1 2 1 2 1 2 1 2 2 3 5 1 2 1 2 1 2 1 2 2 2 6 1 2 1 2 1 2 1 2 2 2 2 2 6 1 3 1 3 1 3 1 3 2 3 3 3 6 1 2 1 2 1 2 1 2 2 2 2 3 6 1 3 1 3 1 3 1 3 2 3...
output:
1 1 1 1 1 1 2 2 2 2 2 3 2 3 2 2 3 3 3 3 3 2 2 3 3 3 3 3 2 2 2 3 2 3 3 3 4 3 4 2 2 3 3 3 3 3 3 3 4 4 4 4 4 2 2 2 3 3 3 3 3 3 3 3 3 4 3 4 4 4 4 4 3 3 4 4 4 4 4 4 4 4 4 3 3 4 4 4 4 4 4 4 4 4 3 3 4 3 4 3 3 4 4 4 4 4 2 2 2 3 3 3 3 3 3 3 3 3 4 3 4 4 4 4 4 3 3 3 4 4 3 4 4 4 4 4 3 3 4 4 4 4 4 4 4 4 4 3 3 4 ...
result:
wrong answer 13th numbers differ - expected: '3', found: '2'