QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#98940#6327. Count Arithmetic ProgressionHOLICWA 69ms8080kbC++143.1kb2023-04-21 00:08:102023-04-21 00:08:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-21 00:08:12]
  • 评测
  • 测评结果:WA
  • 用时:69ms
  • 内存:8080kb
  • [2023-04-21 00:08:10]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 1009;
const int mod = 998244353;
#define int long long
const int inv = (mod + 1) / 2;
#define ll long long
struct CHT{
    const ll inf = 0x7f7f7f7f7f7f7f7f;
    struct line{
        ll k, b;
        line() {}
        line(ll k, ll b) : k(k), b(b) {}
        double intersect(line l) {return 1.0 * (l.b - b) / (k - l.k);}
        ll operator () (ll x) {return k * x + b;}
    };
    vector<double> x;
    vector<line> li;
    void init(line l) {
        x.push_back({-inf}); li.push_back(l);
    }
    void addline(line l) {
        while(li.size() >= 2 && l.intersect(li[li.size() - 2]) <= x.back()) {
            x.pop_back(); li.pop_back();
        }
        if(!li.empty()) x.push_back(l.intersect(li.back()));
        li.push_back(l);
    }
    ll query(ll qx) {
        int id = upper_bound(x.begin(), x.end(), qx) - x.begin();
        return li[id - 1](qx);
    }
}up, down;
//维护一次函数的最小值,即维护上凸包,插入y=kx+b时,按k的降序插入
//维护一次函数的最大值,即维护下凸包,插入y=kx+b时,按k的升序插入
int n;
ll L[N], R[N];
void work() {
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> L[i];
    for(int i = 0; i < n; i ++) cin >> R[i];
    up.init({0, R[0]});
    for(int i = 1; i < n; i ++) up.addline({-i, R[i]});
    down.init({-(n - 1), L[n - 1]});
    for(int i = n - 2; i >= 0; i --) down.addline({-i, L[i]});
    vector<int> ver;
    up.x.erase(up.x.begin());
    down.x.erase(down.x.begin());
    for(auto v : up.x) ver.push_back(ceil(v));
   // for(auto v : up.x) cout << v << endl;
    for(auto v : down.x) ver.push_back(ceil(v));
    sort(ver.begin(), ver.end());
    ver.erase(unique(ver.begin(), ver.end()), ver.end());
    ll from = -1e12, ans = 0;
    int upid = 0, downid = 0;
    ver.push_back(1e12);
    for(auto v : ver) {
        ll xl = from, xr = v;
       // cout <<xl << " " << xr << endl;
        ll UP = -up.li[upid].k;
        ll DOWN = -down.li[downid].k;
       // cout << UP << " " <<DOWN << " " << R[UP] << " "<< L[DOWN] << endl;
        if(UP < DOWN) {
            ll x = ceil(1.0 * (R[UP] - L[DOWN]) / (UP - DOWN));
            xl = max(xl, x);
        }
        if(UP > DOWN){
            ll x = floor(1.0 * (R[UP] - L[DOWN]) / (UP - DOWN));
            xr = min(xr, x + 1);
        }
      //  cout << xl << " " << xr << endl;
        if(xl < xr) {
            ans = ans + (R[UP] - L[DOWN] + 1) % mod * (xr - xl) % mod;
            ans %= mod;
            ans = ans + DOWN * (xr - xl) % mod * inv % mod * (xr + xl - 1) % mod;
            ans = ans - UP * (xr - xl) % mod * inv % mod * (xr + xl - 1) % mod;
        }
        while(upid < up.x.size() && ceil(up.x[upid]) == xr) upid ++;
        while(downid < down.x.size() && ceil(down.x[downid]) == xr) downid ++;
        from = xr;
       // cout << ans <<"!!!!" << endl;
    }
    cout << (ans % mod + mod) % mod << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int Case = 1;
    while(Case --) work();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 5432kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 2ms
memory: 5420kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: 0
Accepted
time: 69ms
memory: 8080kb

input:

300000
121398540794 60081434790 252920491076 43666218735 95583832019 21178121624 315727133812 89837170656 138389231466 174687947367 124350262341 108583578309 289629745492 321006985392 301201031648 138149017169 255983300245 138801256482 285614769875 130583757928 261690466826 74624776159 303504239011 ...

output:

2000014

result:

ok 1 number(s): "2000014"

Test #4:

score: -100
Wrong Answer
time: 3ms
memory: 5332kb

input:

2
1 1
1000000000000 1000000000000

output:

138519916

result:

wrong answer 1st numbers differ - expected: '276262510', found: '138519916'