QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#553842#8556. Somewhere Over the RainbowPurslaneWA 1ms5604kbC++141019b2024-09-08 21:10:512024-09-08 21:10:53

Judging History

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

  • [2024-09-08 21:10:53]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5604kb
  • [2024-09-08 21:10:51]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,m,x[MAXN],y[MAXN];
__int128 sum;
struct INFO {int x,y,k;__int128 sum;};
stack<INFO> st;
void insert(int X,int Y) {
	while(!st.empty()) {
		__int128 x=st.top().x,y=st.top().y,k=st.top().k;
		__int128 Ymx=y+(X-x)*k-(X-x)*(X-x+1)/2; 
		if(Ymx<Y) {st.pop();continue ;}
		__int128 dt=Ymx-Y,del=dt/(X-x),d=X-x;
		__int128 sum=y*d+k*d+k*d*d-(k+d+1)*d*(d+1)/2+d*(d+1)*(d+d+1)/6;
		sum-=del*(d*(d+1)/2),k-=del;
		k-=d;
		if(dt%d) dt%=d,sum-=d*(d+1)/2,k--;	
		st.push({X,Y,k,sum});
		break ;
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	ffor(i,1,n) cin>>x[i]>>y[i];
	st.push({0,0,(__int128)100000000000000000000,0});
	ffor(i,1,n) insert(x[i],y[i]);
	insert(m,0);
	while(!st.empty()) sum+=st.top().sum,st.pop();
	cout<<(int)(sum%998244353);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 3620kb

input:

0 5

output:

10

result:

ok 1 number(s): "10"

Test #3:

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

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:

9775

result:

wrong answer 1st numbers differ - expected: '10725', found: '9775'