QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#116696#4193. Joined SessionswsyearWA 3ms15844kbC++143.1kb2023-06-29 20:11:122023-06-29 20:11:15

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-29 20:11:15]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:15844kb
  • [2023-06-29 20:11:12]
  • 提交

answer

/*
* Author: Enucai
* Date: 2022-12-13 09:51:34
* LastEditTime: 2023-06-29 20:11:34
*/

#include <bits/stdc++.h>
#ifdef dbg
#define D(...) fprintf(stderr, __VA_ARGS__)
#define DD(...) D(#__VA_ARGS__ " = "), debug_helper::debug(__VA_ARGS__), D("\n")
#include "C:\Users\wsyear\Desktop\OI\templates\debug.hpp"
#else
#define D(...) ((void)0)
#define DD(...) ((void)0)
#endif
#define rep(i, j, k) for (int i = (j); i <= (k); ++i)
#define per(i, j, k) for (int i = (j); i >= (k); --i)
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define gc getchar
#define pc putchar
using ll = long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

using namespace std;

template <class T = int> T read() {
  T x = 0; bool f = 0; char ch = gc();
  while (!isdigit(ch)) f = ch == '-', ch = gc();
  while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = gc();
  return f ? -x: x;
}
template <class T> void write(T x) {
  if (x >= 0) { if (x > 9) write(x / 10); pc(x % 10 + 48); }
  else { pc('-'); if (x < -9) write(-x / 10); pc(48 - x % 10); }
}

const int N = 1000010;
const int M = 2000010;

struct SegMent {
  int l, r;
} a[N];

int n, c[M], f[N][4], g[4], lst[N], con[N], t[M << 2], sm[N];

#define mid ((l + r) >> 1)

void upd(int c, int l, int r, int x, int v) {
  if (l == r) return t[c] = v, void();
  if (x <= mid) upd(c << 1, l, mid, x, v);
  else upd(c << 1 | 1, mid + 1, r, x, v);
  t[c] = max(t[c << 1], t[c << 1 | 1]);
}

int qry(int c, int l, int r, int x, int y) {
  if (l == x && r == y) return t[c];
  if (y <= mid) return qry(c << 1, l, mid, x, y);
  else if (x > mid) return qry(c << 1 | 1, mid + 1, r, x, y);
  else return max(qry(c << 1, l, mid, x, mid), qry(c << 1 | 1, mid + 1, r, mid + 1, y));
}

#undef mid

int main() {
  n = read();
  rep (i, 1, n) a[i].l = read(), a[i].r = read();
  sort(a + 1, a + n + 1, [&](SegMent x, SegMent y) {
    return x.r == y.r ? x.l < y.l : x.r < y.r;
  });
  bool flag = 0;
  rep (i, 1, n - 1) if (a[i].r >= a[i + 1].l) flag = 1;
  if (!flag) return puts("impossible"), 0;
  rep (i, 1, n) c[2 * i - 1] = a[i].l, c[2 * i] = a[i].r;
  sort(c + 1, c + 2 * n + 1);
  rep (i, 1, n) {
    a[i].l = lower_bound(c + 1, c + 2 * n + 1, a[i].l) - c;
    a[i].r = lower_bound(c + 1, c + 2 * n + 1, a[i].r) - c;
  }
  rep (i, 1, n << 3) t[i] = 0;
  rep (i, 1, n) {
    if (a[i].l != 1) lst[i] = qry(1, 1, n << 1, 1, a[i].l - 1);
    upd(1, 1, n << 1, a[i].r, i);
  }
  rep (i, 1, n << 3) t[i] = 0;
  rep (i, 1, n) {
    con[i] = qry(1, 1, n << 1, a[i].l, a[i].r);
    upd(1, 1, n << 1, a[i].r, i);
  }
  rep (i, 0, n) rep (j, 0, 3) f[i][j] = 1E9;
  f[0][0] = 0;
  rep (i, 1, n) rep (j, 0, 3) {
    f[i][j] = f[lst[i]][j] + 1;
    int pos = i;
    rep (k, 1, j) {
      pos = con[pos];
      if (!pos) break;
      f[i][j] = min(f[i][j], f[pos][j - k]);
    }
  }
  per (i, n, 1) sm[i] = max(sm[i + 1], a[i].l);
  rep (i, 0, 3) g[i] = 1E9;
  rep (i, 1, n) rep (j, 0, 3) if (a[i].r >= sm[i + 1]) g[j] = min(g[j], f[i][j]);
  rep (i, 1, 3) if (g[i] < g[0]) return write(i), 0;
  puts("impossible");
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 15844kb

input:

4
1 3
2 5
4 7
6 9

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 3ms
memory: 15672kb

input:

5
1 3
4 7
8 10
2 5
6 9

output:

2

result:

ok single line: '2'

Test #3:

score: 0
Accepted
time: 1ms
memory: 15628kb

input:

3
1 2
2 3
3 4

output:

impossible

result:

ok single line: 'impossible'

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 15684kb

input:

6
1 3
2 5
4 7
6 9
8 11
10 12

output:

1

result:

wrong answer 1st lines differ - expected: '3', found: '1'