QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#878405#9982. Staircase MuseumzlxFTHWA 5ms3712kbC++17904b2025-02-01 15:10:182025-02-01 15:10:20

Judging History

This is the latest submission verdict.

  • [2025-02-01 15:10:20]
  • Judged
  • Verdict: WA
  • Time: 5ms
  • Memory: 3712kb
  • [2025-02-01 15:10:18]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define sz(a) int(a.size())

template<class T> void cmax(T &a, const T &b) {a = max(a, b);}
template<class T> void cmin(T &a, const T &b) {a = min(a, b);}

void solve() {
  int n;
  cin >> n;
  vector<int> l(n), r(n);
  vector<int> a(n), b(n);
  a[0] = b[0] = 1;
  int j = 0;
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    if (!i) continue;
    while (j < i && r[j] < l[i]) j++;
    if (r[i - 1] != r[i]) {
      a[i] = max(a[i - 1], b[i - 1]) + 1;
    }
    if (l[i - 1] != l[i]) {
      b[i] = max(a[min(j, i - 1)], b[i - 1]) + 1;
    }
    cmax(a[i], a[i - 1]);
    cmax(b[i], b[i - 1]);
  }
  cout << max(a[n - 1], b[n - 1]) << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
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: 5ms
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
3
3
2
2
2
3
3
3
3
2
2
3
3
3
3
3
2
2
2
3
3
3
3
3
4
4
4
3
3
3
4
4
4
4
3
3
4
4
4
4
4
2
2
2
2
3
3
3
3
3
3
2
2
3
3
3
3
3
3
3
3
3
3
4
4
3
3
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
4
3
3
4
4
4
4
4
2
2
2
3
3
3
3
3
3
3
3
3
4
4
4
4
4
4
4
3
3
3
4
4
3
3
4
4
4
4
3
3
4
4
4
4
4
4
4
4
4
3
3
4
...

result:

wrong answer 20th numbers differ - expected: '2', found: '3'