QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #546602 | #8556. Somewhere Over the Rainbow | strlen_s_ | RE | 1ms | 5732kb | C++17 | 1.2kb | 2024-09-04 10:03:51 | 2024-09-04 10:03:56 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull long long
using namespace std;
const int N=1e5+10,mod=998244353;
const ull inf=1e9;
struct node{
ull x,y,d;
};
node st[N];
int top;
int n,m,res;
struct put{
ll x,y;
}p[N];
ull ans;
ull calc(ull h,ull len,ull d){return (h+h+(len-1)*d)*len/2;}
ull calc2(ull d,ull len){return d*len*len+(len-1)*len*(2*len-1)/6-(len+d)*len*(len-1)/2;}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;
p[++n]=(put){0,0},p[++n]=(put){m,0};
sort(p+1,p+1+n,[&](put x,put y){return x.x<y.x;});
st[++top]=(node){0,0,inf};
for(int i=2;i<=n;i++){
ull d=0;
while(top){
node x=st[top];
ull dis=p[i].x-x.x;
if(x.y+calc(x.d-1,dis,-1)<p[i].y){top--;continue;}
ull c=x.y+calc(x.d-1,dis,-1)-p[i].y;
d=x.d-dis-(c-1)/dis-1;
break;
}
st[++top]=(node){p[i].x,p[i].y,d};
}
for(int i=2;i<=top;i++){
node x=st[i-1],y=st[i];
ull dis=y.x-x.x,c=x.y+calc(x.d-1,dis,-1)-y.y;
ans+=x.y*dis+calc2(x.d-1,dis);
ull s=c/dis,r=c%dis;
ans+=calc(-1,dis,-1)*s+calc(-1,r,-1);
}
res=ans%mod;
cout<<res<<'\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5648kb
input:
3 6 1 100 4 42 5 22
output:
310
result:
ok 1 number(s): "310"
Test #2:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
0 5
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 1ms
memory: 5624kb
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: 1ms
memory: 5688kb
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: 1ms
memory: 5648kb
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: 0
Accepted
time: 1ms
memory: 5620kb
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:
674709
result:
ok 1 number(s): "674709"
Test #7:
score: 0
Accepted
time: 0ms
memory: 3564kb
input:
100 250 1 99 2 176 4 122 5 16 6 138 7 59 9 134 10 185 11 249 12 245 13 148 14 9 15 74 20 190 23 203 24 239 31 41 32 202 33 155 37 26 40 170 43 84 45 144 46 59 47 169 54 184 56 37 57 106 58 38 60 219 63 40 66 245 68 106 70 97 72 127 74 146 75 1 76 173 77 179 79 205 81 72 83 90 85 17 88 227 90 163 92 ...
output:
1309875
result:
ok 1 number(s): "1309875"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
120 300 5 37 6 246 13 248 14 152 15 250 16 221 17 201 20 171 21 73 23 97 24 163 26 168 28 228 29 57 31 193 32 226 34 7 35 81 39 78 41 120 42 290 44 228 47 192 49 269 50 86 52 222 54 91 55 37 59 94 61 24 62 200 65 221 68 119 72 230 75 20 76 160 77 288 81 32 84 84 85 19 88 22 94 240 98 135 99 284 102 ...
output:
2261225
result:
ok 1 number(s): "2261225"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5624kb
input:
140 350 1 82 3 115 4 59 7 212 9 307 10 149 18 189 19 43 21 77 22 264 25 177 29 117 31 49 32 181 33 231 34 45 35 152 41 314 42 258 43 276 44 33 45 114 48 119 49 323 59 100 60 26 61 40 63 304 64 343 65 277 67 138 74 234 78 188 79 59 80 213 81 257 83 197 84 76 94 286 96 72 97 225 98 14 101 154 102 202 ...
output:
3588200
result:
ok 1 number(s): "3588200"
Test #10:
score: 0
Accepted
time: 1ms
memory: 5592kb
input:
160 400 3 76 4 29 7 25 16 73 18 76 19 368 21 311 23 111 25 298 26 51 28 396 29 11 31 213 32 284 35 395 36 214 37 256 40 216 41 178 44 101 46 382 47 286 49 64 52 184 56 113 57 247 59 308 64 393 66 392 67 46 68 256 69 230 76 153 78 263 80 396 84 9 87 3 93 373 94 35 95 48 97 305 98 310 105 2 106 94 109...
output:
5353300
result:
ok 1 number(s): "5353300"
Test #11:
score: 0
Accepted
time: 0ms
memory: 5608kb
input:
180 450 6 384 9 255 10 135 11 389 12 355 13 170 14 87 15 355 16 295 17 397 19 244 20 238 22 61 28 346 31 411 32 315 34 220 36 133 38 47 41 21 42 99 43 354 44 212 45 368 50 85 52 99 55 147 58 119 59 24 66 349 67 103 69 77 73 97 76 339 77 417 80 175 82 343 88 265 90 184 91 225 92 269 93 301 94 35 95 2...
output:
7619025
result:
ok 1 number(s): "7619025"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5660kb
input:
200 500 2 302 4 37 14 133 16 148 18 138 19 61 21 206 24 361 25 417 26 171 27 70 29 314 30 43 31 231 34 341 37 373 39 144 43 371 44 239 46 494 49 159 51 18 53 163 56 167 57 446 60 215 62 381 63 116 64 37 67 382 69 375 71 331 77 125 79 432 81 256 83 130 84 333 86 264 89 31 91 27 93 340 94 366 95 315 9...
output:
10447875
result:
ok 1 number(s): "10447875"
Test #13:
score: -100
Runtime Error
input:
123748 1237481 10 3247552102 14 4546572905 15 4871328114 18 5845593708 29 9417900801 31 10067411175 34 11041676717 37 12015942260 50 16237759481 58 18835800760 67 21758597131 72 23382372855 73 23707127994 78 25330903696 86 27928944751 90 29227965263 129 41893414353 132 42867679610 142 46115230387 15...