QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#282100 | #7872. 崩坏天际线 | hos_lyric# | 10 | 2ms | 3964kb | C++14 | 5.9kb | 2023-12-11 13:28:48 | 2024-07-04 03:12:21 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
////////////////////////////////////////////////////////////////////////////////
template <unsigned M_> struct ModInt {
static constexpr unsigned M = M_;
unsigned x;
constexpr ModInt() : x(0U) {}
constexpr ModInt(unsigned x_) : x(x_ % M) {}
constexpr ModInt(unsigned long long x_) : x(x_ % M) {}
constexpr ModInt(int x_) : x(((x_ %= static_cast<int>(M)) < 0) ? (x_ + static_cast<int>(M)) : x_) {}
constexpr ModInt(long long x_) : x(((x_ %= static_cast<long long>(M)) < 0) ? (x_ + static_cast<long long>(M)) : x_) {}
ModInt &operator+=(const ModInt &a) { x = ((x += a.x) >= M) ? (x - M) : x; return *this; }
ModInt &operator-=(const ModInt &a) { x = ((x -= a.x) >= M) ? (x + M) : x; return *this; }
ModInt &operator*=(const ModInt &a) { x = (static_cast<unsigned long long>(x) * a.x) % M; return *this; }
ModInt &operator/=(const ModInt &a) { return (*this *= a.inv()); }
ModInt pow(long long e) const {
if (e < 0) return inv().pow(-e);
ModInt a = *this, b = 1U; for (; e; e >>= 1) { if (e & 1) b *= a; a *= a; } return b;
}
ModInt inv() const {
unsigned a = M, b = x; int y = 0, z = 1;
for (; b; ) { const unsigned q = a / b; const unsigned c = a - q * b; a = b; b = c; const int w = y - static_cast<int>(q) * z; y = z; z = w; }
assert(a == 1U); return ModInt(y);
}
ModInt operator+() const { return *this; }
ModInt operator-() const { ModInt a; a.x = x ? (M - x) : 0U; return a; }
ModInt operator+(const ModInt &a) const { return (ModInt(*this) += a); }
ModInt operator-(const ModInt &a) const { return (ModInt(*this) -= a); }
ModInt operator*(const ModInt &a) const { return (ModInt(*this) *= a); }
ModInt operator/(const ModInt &a) const { return (ModInt(*this) /= a); }
template <class T> friend ModInt operator+(T a, const ModInt &b) { return (ModInt(a) += b); }
template <class T> friend ModInt operator-(T a, const ModInt &b) { return (ModInt(a) -= b); }
template <class T> friend ModInt operator*(T a, const ModInt &b) { return (ModInt(a) *= b); }
template <class T> friend ModInt operator/(T a, const ModInt &b) { return (ModInt(a) /= b); }
explicit operator bool() const { return x; }
bool operator==(const ModInt &a) const { return (x == a.x); }
bool operator!=(const ModInt &a) const { return (x != a.x); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x; }
};
////////////////////////////////////////////////////////////////////////////////
constexpr unsigned MO = 998244353;
using Mint = ModInt<MO>;
// root: min (tie-break: left)
struct MinCartesianTree {
int n, rt;
vector<int> par, lef, rig;
template <class T> void build(int n_, T *as) {
assert(n_ >= 1);
n = n_;
rt = 0;
par.assign(n, -1);
lef.assign(n, -1);
rig.assign(n, -1);
int top = 0;
vector<int> stack(n, 0);
for (int u = 1; u < n; ++u) {
if (as[stack[top]] > as[u]) { // >
for (; top >= 1 && as[stack[top - 1]] > as[u]; --top) {} // >
if (top == 0) {
rt = par[lef[u] = stack[top]] = u;
} else {
par[lef[u] = stack[top]] = u;
rig[par[u] = stack[top - 1]] = u;
}
stack[top] = u;
} else {
rig[par[u] = stack[top]] = u;
stack[++top] = u;
}
}
}
template <class T> void build(const T &as) {
build(as.size(), as.data());
}
};
int N, Q;
vector<int> O, L, R, X;
namespace brute {
vector<int> qs;
MinCartesianTree ct;
Mint dfs(int l, int r, int u) {
Mint ret = 0;
if (l < u && u < r && qs[u] < Q) {
ret += dfs(l, u, ct.lef[u]);
ret += dfs(u, r, ct.rig[u]);
ret /= 2;
} else {
ret = (r - l);
}
// cerr<<"dfs "<<l<<" "<<r<<" "<<u<<": "<<ret<<endl;
return ret;
}
Mint run() {
cerr<<"[brute::run]"<<endl;
Mint ans = 0;
for (int q = 0; q < Q; ++q) if (O[q] == 1) {
qs.assign(N + 2, Q);
for (int qq = q + 1; qq < Q; ++qq) if (O[qq] == 2) {
if (L[q] < X[qq] && X[qq] < R[q]) {
chmin(qs[X[qq]], qq);
}
}
// cerr<<L[q]<<" "<<R[q]<<" "<<qs<<endl;
ct.build(qs);
ans += dfs(L[q], R[q], ct.rt);
}
return ans;
}
} // brute
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
O.resize(Q);
L.assign(Q, 0);
R.assign(Q, 0);
X.assign(Q, 0);
for (int q = 0; q < Q; ++q) {
scanf("%d", &O[q]);
if (O[q] == 1) {
scanf("%d%d", &L[q], &R[q]);
} else {
scanf("%d", &X[q]);
}
}
Mint ans = 0;
if (N <= 5000 && Q <= 1000) {
ans = brute::run();
} else {
assert(false);
}
printf("%u\n", ans.x);
}
return 0;
}
详细
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 1ms
memory: 3876kb
input:
500 500 1 119 258 2 134 2 417 2 176 2 61 2 60 2 110 1 335 336 1 96 111 2 202 1 138 344 2 358 2 134 1 29 54 1 73 381 1 179 495 2 490 2 418 2 186 2 183 1 168 340 2 78 1 15 27 2 373 1 245 498 1 372 495 2 244 2 63 1 174 490 2 282 2 417 1 272 408 1 109 134 2 303 2 345 1 238 401 1 36 480 1 21 483 2 10 1 3...
output:
855279801
result:
ok single line: '855279801'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3888kb
input:
495 466 1 35 393 2 236 1 4 335 2 455 1 36 470 1 23 61 2 195 2 109 2 451 1 282 491 2 238 2 117 2 468 1 2 60 1 439 487 2 238 1 209 294 2 321 2 309 1 113 183 2 409 2 87 2 130 2 124 2 176 2 448 2 379 1 181 446 2 146 2 450 1 171 423 2 355 2 332 1 123 387 1 151 269 1 17 417 2 122 1 324 494 1 265 439 2 225...
output:
294468977
result:
ok single line: '294468977'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
441 467 2 180 1 51 344 2 180 1 16 345 1 39 419 1 64 432 2 176 1 35 372 2 426 1 8 415 1 1 439 1 17 430 2 433 1 89 369 1 83 353 2 292 1 1 421 1 63 430 1 33 345 1 69 421 1 49 373 1 77 343 1 24 393 1 90 375 1 8 425 2 322 2 61 2 112 2 209 1 39 406 1 12 426 1 29 430 1 50 374 1 47 394 1 9 387 2 234 1 19 35...
output:
526117259
result:
ok single line: '526117259'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3872kb
input:
500 500 2 442 1 12 414 1 40 435 2 138 1 79 448 1 16 464 2 163 1 94 492 2 97 2 335 1 7 452 1 25 474 1 78 442 2 286 1 93 430 1 78 438 2 469 2 354 2 270 2 292 2 108 2 301 1 100 480 2 258 1 17 487 2 2 2 409 2 385 2 338 1 83 454 1 41 490 1 95 475 1 43 442 1 66 445 2 406 2 168 1 10 406 2 330 2 20 1 90 491...
output:
810270061
result:
ok single line: '810270061'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3892kb
input:
500 500 1 29 407 1 89 480 1 31 497 1 28 494 1 21 492 1 91 465 1 13 467 1 89 425 1 22 444 1 20 430 1 48 445 1 33 441 1 61 435 1 69 427 1 89 485 1 90 446 1 23 488 1 6 424 1 76 425 1 36 460 1 16 421 1 20 500 1 3 487 1 99 481 1 53 412 1 96 456 1 39 436 1 28 436 1 4 409 1 9 486 1 22 484 1 88 413 1 26 467...
output:
419428992
result:
ok single line: '419428992'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3804kb
input:
500 500 1 85 442 1 20 473 1 10 441 1 31 426 1 95 478 1 60 454 1 54 491 1 97 464 1 14 443 1 88 474 1 28 462 1 97 410 1 99 496 1 96 493 1 62 479 1 12 466 1 64 471 1 43 490 1 50 411 1 85 448 1 48 433 1 30 456 1 39 462 1 46 409 1 63 494 1 39 409 1 36 436 1 27 463 1 37 498 1 69 464 1 8 441 1 99 436 1 84 ...
output:
519347055
result:
ok single line: '519347055'
Subtask #2:
score: 0
Runtime Error
Dependency #1:
100%
Accepted
Test #7:
score: 0
Runtime Error
input:
5000 5000 2 2254 2 4832 2 208 1 335 3080 2 481 1 527 3659 1 2645 3803 1 855 3544 2 3824 2 347 1 1567 4426 1 2184 4493 2 142 2 2451 1 995 4170 2 576 2 999 2 2726 1 278 3540 2 3218 1 922 3302 2 3253 2 4161 2 4505 1 4201 4534 1 1827 3540 2 3241 2 1909 2 2667 1 723 2453 2 3123 1 1017 4791 1 2953 3384 1 ...
output:
result:
Subtask #3:
score: 0
Runtime Error
Test #13:
score: 0
Runtime Error
input:
50000 50000 1 24367 33007 1 14396 42256 1 6375 22327 1 7892 42501 1 10100 37998 1 6284 48524 1 7357 18164 1 16200 46424 1 18972 34131 1 16849 32591 1 1917 3018 1 19897 30272 1 45044 45753 1 18999 25448 1 5167 31033 1 6182 35335 1 7270 37270 1 12651 39965 1 28896 38022 1 13853 35426 1 35516 48244 1 1...
output:
result:
Subtask #4:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%