QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#117958 | #6673. Be Careful 2 | hos_lyric | TL | 5246ms | 3852kb | C++14 | 8.2kb | 2023-07-02 17:57:40 | 2023-07-02 17:57:41 |
Judging History
answer
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 <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; }
////////////////////////////////////////////////////////////////////////////////
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>;
// Sum[(x - t) (y - t) t^2, {t, 1, s}]
inline Mint func(Mint x, Mint y, Mint s) {
return s * (1+s) * (-2 + 2*s + 18*s*s + 12*s*s*s - 15*s*x -
15*s*s*x - 15*s*y - 15*s*s*y + 10*x*y + 20*s*x*y)
/ 60;
}
// \sum[1<=t] max{X + 1 - t, 0} max{Y + 1 - t, 0} t^2
Mint calc2(Int X, Int Y) {
return func(X + 1, Y + 1, min(X, Y));
}
// \sum[1<=a<=P] \sum[1<=b<=Q] max{Y + 1 - (a+b), 0} (a+b)^2
Mint calc1(Int P, Int Q, Int Y) {
// \sum[A<=t] (t - A + 1) max{Y + 1 - t, 0} t^2
auto sub = [&](Int A) -> Mint {
if (A > Y) return 0;
return -(func(A - 1, Y + 1, Y) - func(A - 1, Y + 1, A - 1));
};
Mint ret = 0;
ret += sub( 1 + 1);
ret -= sub( 1 + Q+1);
ret -= sub(P+1 + 1);
ret += sub(P+1 + Q+1);
return ret;
}
// \sum[1<=a<=P] \sum[1<=b<=Q] \sum[1<=c<=R] \sum[1<=d<=S] [b-a = d-c] (b-a)(d-c)
Mint calc0(Int P, Int Q, Int R, Int S) {
const Int lim = max(P + Q, R + S);
// sum[A<=t && B<=t] (t - A + 1) (t - B + 1) t^2
auto sub = [&](Int A, Int B) -> Mint {
if (max(A, B) > lim) return 0;
return func(A - 1, B - 1, lim) - func(A - 1, B - 1, max(A, B) - 1);
};
Mint ret = 0;
for (int h = 0; h < 1 << 4; ++h) {
Int A = 0, B = 0;
A += ((h >> 0 & 1) ? (P+1) : 1);
A += ((h >> 1 & 1) ? (Q+1) : 1);
B += ((h >> 2 & 1) ? (R+1) : 1);
B += ((h >> 3 & 1) ? (S+1) : 1);
ret += (__builtin_parity(h)?-1:+1) * sub(A, B);
}
return ret;
}
int M, N, K;
vector<int> X, Y;
int main() {
for (; ~scanf("%d%d%d", &M, &N, &K); ) {
X.resize(K);
Y.resize(K);
for (int k = 0; k < K; ++k) {
scanf("%d%d", &X[k], &Y[k]);
}
vector<int> ks(K);
for (int k = 0; k < K; ++k) {
ks[k] = k;
}
sort(ks.begin(), ks.end(), [&](int k0, int k1) -> bool {
return ((Y[k0] != Y[k1]) ? (Y[k0] < Y[k1]) : (X[k0] < X[k1]));
});
auto ms = X;
ms.push_back(0);
ms.push_back(M);
sort(ms.begin(), ms.end());
ms.erase(unique(ms.begin(), ms.end()), ms.end());
const int msLen = ms.size();
Mint ans = 0;
int len;
vector<int> xs(K + 2), ys(K + 2);
vector<int> prv(K + 2), nxt(K + 2);
for (int e = 0; e < msLen - 1; ++e) {
// x1 < xR <= x2
const int x1 = ms[e];
const int x2 = ms[e + 1];
// cerr<<"("<<x1<<", "<<x2<<"]"<<endl;
// Case. x1 <= xL
{
const Mint res = calc2(x2 - x1, N);
ans += res;
/*
Mint brt=0;
for(int a=x1;a<=x2;++a)for(int b=a+1;b<=x2;++b)
for(int c=0;c<=N;++c)for(int d=c+1;d<=N;++d)
if(b-a==d-c)brt+=(b-a)*(d-c);
cerr<<" #"<<__LINE__<<": "<<brt<<" "<<res<<endl;
assert(brt==res);
//*/
}
len = 0;
xs[0] = 0;
ys[0] = 0;
for (const int k : ks) if (X[k] <= ms[e]) {
++len;
xs[len] = X[k];
ys[len] = Y[k];
}
xs[len + 1] = 0;
ys[len + 1] = N;
// cerr<<len<<" "<<xs<<" "<<ys<<endl;
for (int i = 1; i <= len; ++i) {
int &j = prv[i] = i - 1;
for (; j >= 1 && xs[j] <= xs[i]; j = prv[j]) {}
}
for (int i = len; i >= 1; --i) {
int &j = nxt[i] = i + 1;
for (; j <= len && xs[j] < xs[i]; j = nxt[j]) {}
}
// no left bound
for (int i = 0; i <= len; ++i) {
// x0 <= xL < x1 < xR <= x2 && y0 <= yL < yR <= y2
const int x0 = 0;
const int y0 = ys[i];
const int y2 = ys[i + 1];
const Mint res = calc1(x1 - x0, x2 - x1, y2 - y0);
ans += res;
/*
Mint brt=0;
for(int a=x0;a<x1;++a)for(int b=x1+1;b<=x2;++b)
for(int c=y0;c<=y2;++c)for(int d=c+1;d<=y2;++d)
if(b-a==d-c)brt+=(b-a)*(d-c);
cerr<<" #"<<__LINE__<<" "<<x0<<" "<<y0<<" "<<y2<<": "<<brt<<" "<<res<<endl;
assert(brt==res);
//*/
}
for (int i = 1; i <= len; ++i) {
// ks[i] decides the left bound
// x0 <= xL < x1 < xR <= x2 && y0 <= yL < y1 < yR <= y2
const int x0 = xs[i];
const int y0 = ys[prv[i]];
const int y1 = ys[i];
const int y2 = ys[nxt[i]];
const Mint res = calc0(x1 - x0, x2 - x1, y1 - y0, y2 - y1);
ans += res;
/*
Mint brt=0;
for(int a=x0;a<x1;++a)for(int b=x1+1;b<=x2;++b)
for(int c=y0;c<y1;++c)for(int d=y1+1;d<=y2;++d)
if(b-a==d-c)brt+=(b-a)*(d-c);
cerr<<" #"<<__LINE__<<" "<<x0<<" "<<y0<<" "<<y1<<" "<<y2<<": "<<brt<<endl;
assert(brt==res);
//*/
}
}
printf("%u\n", ans.x);
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
3 3 1 2 2
output:
21
result:
ok 1 number(s): "21"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3640kb
input:
5 5 2 2 1 2 4
output:
126
result:
ok 1 number(s): "126"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
6 6 5 4 1 3 2 2 4 1 5 5 3
output:
161
result:
ok 1 number(s): "161"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
15 38 6 12 6 7 15 2 18 3 19 4 2 14 29
output:
80066
result:
ok 1 number(s): "80066"
Test #5:
score: 0
Accepted
time: 1ms
memory: 3648kb
input:
5145 5419 9 547 285 294 284 375 385 217 857 348 925 14 274 3104 853 184 953 794 603
output:
334363567
result:
ok 1 number(s): "334363567"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
5 5 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4
output:
25
result:
ok 1 number(s): "25"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3680kb
input:
9145 9419 12 123 456 223 456 547 285 294 284 375 385 217 857 348 925 14 274 1104 853 184 953 794 603 2234 5678
output:
921360185
result:
ok 1 number(s): "921360185"
Test #8:
score: 0
Accepted
time: 1ms
memory: 3652kb
input:
6 8 4 2 3 3 3 4 2 1 1
output:
444
result:
ok 1 number(s): "444"
Test #9:
score: 0
Accepted
time: 1757ms
memory: 3800kb
input:
1000000000 1000000000 5000 1657 1 1644 1 1000000 116362 1186 1 2392 1 1560 1 995 1 2340 1 1916 1 2143 1 1762 1 1000000 116109 1651 1 1000000 116059 2289 1 1000000 115730 1000000 115896 1000000 116499 1608 1 342 1 1000000 116949 1965 1 1000000 114571 1000000 116602 2171 1 1000000 114848 1000000 11627...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #10:
score: 0
Accepted
time: 5246ms
memory: 3812kb
input:
1000000000 1000000000 5000 1 2581 1 2273 115983 1000000 116105 1000000 114552 1000000 1 1955 1 2254 116061 1000000 116182 1000000 115783 1000000 114564 1000000 116614 1000000 116229 1000000 116087 1000000 114956 1000000 1 2453 114766 1000000 115750 1000000 115448 1000000 1 1748 116665 1000000 1 2237...
output:
80025633
result:
ok 1 number(s): "80025633"
Test #11:
score: 0
Accepted
time: 776ms
memory: 3816kb
input:
1000000000 1000000000 5000 824 1 811 1 2300000 114696 353 1 1559 1 727 1 162 1 1507 1 1083 1 1310 1 929 1 1000000 116109 818 1 1000000 116059 1456 1 1000000 115730 1000000 115896 2300000 114833 775 1 2300000 115576 2300000 115283 1132 1 1000000 114571 2300000 114936 1338 1 1000000 114848 2300000 114...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #12:
score: 0
Accepted
time: 3096ms
memory: 3772kb
input:
1000000000 1000000000 5000 1 1748 1 1440 115983 1000000 116105 1000000 114552 1000000 1 1122 1 1421 116061 1000000 114516 2300000 115783 1000000 114564 1000000 114948 2300000 114563 2300000 116087 1000000 114956 1000000 1 1620 114766 1000000 115750 1000000 115448 1000000 1 915 114999 2300000 1 1404 ...
output:
537083161
result:
ok 1 number(s): "537083161"
Test #13:
score: 0
Accepted
time: 7ms
memory: 3804kb
input:
1000000000 1000000000 5000 2300000 115622 1000000 116216 1000000 116852 2300000 115827 2300000 116715 1000000 116212 2300000 116390 2300000 114646 1000000 114857 2300000 116404 1000000 116398 1000000 115409 2300000 115721 1000000 116136 2300000 114925 2300000 114869 2300000 116176 1000000 115774 100...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #14:
score: 0
Accepted
time: 3459ms
memory: 3848kb
input:
1000000000 1000000000 5000 116495 1000000 116269 1000000 115204 2300000 115724 1000000 116508 1000000 115095 2300000 116712 1000000 114789 2300000 115009 2300000 114795 1000000 115093 2300000 115612 1000000 116183 2300000 116140 2300000 116148 2300000 115608 2300000 115111 1000000 115058 1000000 115...
output:
129612365
result:
ok 1 number(s): "129612365"
Test #15:
score: 0
Accepted
time: 152ms
memory: 3852kb
input:
999999992 999999990 5000 1035170 5702575 3959104 3959104 3887901 7432303 11377527 9794948 6282049 47695 11781994 2037659 11292228 47695 6787467 878630 10441683 5492431 1240650 1129736 5631557 11377527 4863442 5631557 6662382 4863442 8837935 7070049 8837935 10441683 4878561 5702575 5610718 2664505 58...
output:
892807048
result:
ok 1 number(s): "892807048"
Test #16:
score: -100
Time Limit Exceeded
input:
999999948 999999898 5000 6033860 10854965 57219333 28077882 18498300 33290576 34559919 16960059 40765867 73389700 9985342 17984966 54717579 26853732 13059544 23513592 56562634 27758141 19776481 35613289 6632028 11929378 14942564 7329745 7337824 13208993 33584464 60460021 13330979 6539654 32561958 58...