QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#554929#8556. Somewhere Over the RainbowPhantomThreshold#WA 0ms3836kbC++202.4kb2024-09-09 18:08:112024-09-09 18:08:11

Judging History

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

  • [2024-09-09 18:08:11]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3836kb
  • [2024-09-09 18:08:11]
  • 提交

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'