QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#554929 | #8556. Somewhere Over the Rainbow | PhantomThreshold# | WA | 0ms | 3836kb | C++20 | 2.4kb | 2024-09-09 18:08:11 | 2024-09-09 18:08:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline long long poww(long long x,long long y,long long mod){
long long ret=1;
while (y){
if (y&1) ret=ret*x,ret%=mod;
x*=x,x%=mod;
y>>=1;
}
return ret;
}
inline long long inv(long long x,long long mod){return poww(x,mod-2,mod);}
const ll mod=998244353;
const ll inv2=(mod+1)/2;
ll inv6=inv(6,mod);
const int maxn=200000;
ll n,m;
pair<ll,ll> a[maxn+50];
pair<ll,ll> operator - (const pair<ll,ll> &A,const pair<ll,ll> &B){
return make_pair(A.first-B.first,A.second-B.second);
}
__int128 cross(const pair<ll,ll> &A,const pair<ll,ll> &B){
return (__int128)A.first*B.second-(__int128)A.second*B.first;
}
int main(){
ios_base::sync_with_stdio(false);
cin >> n >> m;
for (ll i=1;i<=n;i++){
cin >> a[i].first >> a[i].second;
a[i].second+=i*(i+1)/2;
}
a[0]=make_pair(0LL,0LL);
a[n+1]=make_pair(m,m*(m+1)/2);
vector<pair<ll,ll>> stk;
for (int i=0;i<=n+1;i++){
while (stk.size()>=2 && cross(stk[stk.size()-1]-stk[stk.size()-2],a[i]-stk[stk.size()-1])>=0) stk.pop_back();
stk.push_back(a[i]);
}
// for (auto [x,y]:stk) cerr << "(" << x << "," << y << ")" << endl;
vector<pair<ll,ll>> vk;
{
int sz=(int)stk.size();
for (int i=1;i<sz;i++){
auto [x,y]=stk[i]-stk[i-1];
bool flag=0;
if (x<0){flag=1;x=-x;}
ll k=y/x;
ll r=y%x;
if (!flag){
if (r>0) vk.emplace_back(k+1,r);
vk.emplace_back(k,x-r);
}
else{
vk.emplace_back(-(k),x-r);
if (r>0) vk.emplace_back(-(k+1),r);
}
}
}
sort(vk.begin(),vk.end(),greater<pair<ll,ll>>());
// for (auto [k,cnt]:vk) cerr << k << "," << cnt << endl;
__int128 presum=0;
ll ans=0;
for (auto [k,cnt]:vk){
__int128 tmp=((presum+k)+(presum+k*cnt))*cnt/2;
tmp=tmp%mod;
if (tmp<0) tmp+=mod;
ans=(ans+tmp)%mod;
presum=(presum+k*cnt)%mod;
if (presum<0) presum+=mod;
}
// for (ll i=1;i<=m;i++){
// ans=(ans+mod-(i*(i+1)/2)%mod)%mod;
// }
{
ans=ans-(m+2)*(m+1)%mod*m%mod*inv6%mod;
ans=ans%mod;
if (ans<0) ans+=mod;
}
cout << ans << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3528kb
input:
3 6 1 100 4 42 5 22
output:
310
result:
ok 1 number(s): "310"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
20 50 4 11 7 4 8 20 13 9 14 29 15 26 16 19 18 18 29 46 30 7 34 37 35 16 38 14 39 47 40 18 42 30 43 6 44 23 47 13 48 4
output:
10725
result:
ok 1 number(s): "10725"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
40 100 3 20 4 67 5 62 7 75 9 49 11 14 14 31 18 11 19 5 24 98 25 100 28 35 30 19 31 20 32 71 37 29 38 5 40 94 45 95 46 65 51 2 52 52 53 61 54 77 57 50 59 69 61 30 65 50 67 4 68 56 73 99 75 15 76 47 78 52 79 72 83 91 88 44 89 3 91 55 94 2
output:
84575
result:
ok 1 number(s): "84575"
Test #5:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
60 150 1 119 4 135 5 75 9 13 11 72 15 34 17 130 21 12 26 107 30 133 33 18 34 135 36 78 37 95 38 26 42 24 44 25 51 49 52 73 54 40 55 100 56 67 61 128 62 87 74 131 75 103 77 84 78 37 81 51 82 83 83 89 84 58 89 117 93 148 94 127 95 118 96 103 97 49 98 28 99 83 102 65 105 97 107 103 109 9 113 40 116 107...
output:
286360
result:
ok 1 number(s): "286360"
Test #6:
score: -100
Wrong Answer
time: 0ms
memory: 3836kb
input:
80 200 3 165 5 49 10 42 11 7 12 115 13 78 14 52 15 102 17 132 18 181 19 36 21 59 23 139 24 8 25 54 26 181 29 178 33 120 37 163 38 90 41 182 44 133 48 171 50 60 52 74 53 174 58 156 61 65 64 156 66 174 67 24 70 64 73 57 77 179 80 5 84 38 86 152 90 153 94 137 96 24 99 59 101 180 103 156 109 29 111 55 1...
output:
671650
result:
wrong answer 1st numbers differ - expected: '674709', found: '671650'