QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#861400#9982. Staircase Museumucup-team5243#WA 7ms3712kbC++171.7kb2025-01-18 17:18:552025-01-18 17:18:55

Judging History

This is the latest submission verdict.

  • [2025-01-18 17:18:55]
  • Judged
  • Verdict: WA
  • Time: 7ms
  • Memory: 3712kb
  • [2025-01-18 17:18:55]
  • Submitted

answer

#ifdef NACHIA
#define _GLIBCXX_DEBUG
#else
#define NDEBUG
#endif
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<int(n); i++)
const i64 INF = 1001001001001001001;
template<typename A> void chmin(A& l, const A& r){ if(r < l) l = r; }
template<typename A> void chmax(A& l, const A& r){ if(l < r) l = r; }
using namespace std;


void testcase(){
    i64 N; cin >> N;
    vector<i64> L(N), R(N); rep(i,N) cin >> L[i] >> R[i];
    rep(i,N) L[i]--;
    {
        i64 f = L[0];
        for(auto& a : L) a -= f;
        for(auto& a : R) a -= f;
    }
    i64 x = R.back();
    i64 ans = 0;
    rep(t,2){
        vector<i64> dpU(N+1), dpD(N+1);
        dpU[0] = dpD[0] = 1;
        rep(i,N-1){
            chmax(dpU[i+1], dpU[i] + (R[i]==R[i+1]?0:1));
            chmax(dpD[i+1], dpD[i] + (L[i]==L[i+1]?0:1));
            if(R[i] != R[i+1]) chmax(dpU[i+1], dpD[i] + 1);
            i64 f = upper_bound(L.begin(), L.end(), R[i]) - L.begin();
            //cout << "i = " << i << " , f = " << f << endl;
            chmax(dpD[f-1], dpD[i] + 1);
        }
        chmax(ans, dpU[N-1]);
        chmax(ans, dpD[N-1]);
        //for(auto a : dpD){ cout << a << " "; } cout << endl;
        //for(auto a : dpU){ cout << a << " "; } cout << endl;

        reverse(L.begin(), L.end());
        reverse(R.begin(), R.end());
        for(auto& a : L) a = x - a;
        for(auto& a : R) a = x - a;
        swap(L,R);
    }

    cout << ans << "\n";
}

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    i64 T; cin >> T; rep(t,T) testcase();
    return 0;
}

詳細信息

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
2
2
2
2
2
2
3
3
2
3
3
3
3
3
3
3
4
4
3
4
3
3
3
4
4
3
4
2
3
3
3
3
3
3
4
4
4
4
3
3
3
4
4
3
4
3
4
4
4
4
4
4
3
3
3
3
4
4
3
4
4
4
3
3
3
4
4
3
4
4
4
4
4
4
5
5
4
4
5
5
4
5
4
4
4
5
5
4
4
5
5
4
5
3
3
4
4
4
4
4
4
5
5
4
5
3
3
3
3
4
4
3
4
4
4
3
4
4
4
4
4
4
4
4
4
4
4
5
5
4
4
5
5
4
5
4
4
4
5
5
4
4
5
5
4
5
3
4
4
...

result:

wrong answer 2nd numbers differ - expected: '1', found: '2'