QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#115993#6327. Count Arithmetic ProgressionxaphoenixWA 52ms11424kbC++173.8kb2023-06-27 21:23:532023-06-27 21:23:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-27 21:23:54]
  • 评测
  • 测评结果:WA
  • 用时:52ms
  • 内存:11424kb
  • [2023-06-27 21:23:53]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC k << 1
#define RC k << 1 | 1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = n - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)

typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, LL> pii;

const int N = 310000;
const int M = 610000;
const int mod = 1e9+7;
const int inf = (int)1e9;
const LL INF = (LL)1e18;
const double eps = 1e-9;
const double pi = acos(-1.0);


inline int dcmp(double x) {
    return (x > eps) - (x < -eps);
}
struct Point {
    double x, y;
    Point (double x = 0 , double y = 0) : x(x) , y(y) {}
    void input() {
        scanf("%lf%lf",&x,&y);
    }
    bool operator < (const Point& R) const {
        if (dcmp(x - R.x) == 0)
            return dcmp(y - R.y) < 0;
        return dcmp(x - R.x) < 0;
    }
    bool operator == (const Point& R) const {
        return dcmp(x - R.x) == 0 && dcmp(y - R.y) == 0;
    }
    Point operator + (const Point& R) const {
        return Point(x + R.x, y + R.y);
    }
    Point operator - (const Point& R) const {
        return Point(x - R.x, y - R.y);
    }
    Point operator * (const double& R) const {
        return Point(x * R, y * R);
    }
    Point operator / (const double& R) const {
        return Point(x / R, y / R);
    }
    double operator ^ (const Point& R) const {
        return x * R.y - y * R.x;
    }
    double operator % (const Point& R) const {
        return x * R.x + y * R.y;
    }
    double len() {
        return sqrt(*this % *this);
    }
    double angle() {
        return atan2(y, x);
    }
};


int n, tp[2];
LL l[2][N];
pii h[2][N]; 
vector<LL> pos;

bool check(pii a, pii b, pii c, int k) {
	pii d; d.fi = b.fi - a.fi; d.se = b.se - a.se;
	return (- d.se * c.fi + d.fi * c.se <= - d.se * b.fi + d.fi * b.se) == k;
}

__int128 eval(pii a, LL x) {
	__int128 cur = x;
	x *= -a.fi; x += a.se;
	return x;
}

int main()
{
	IO;
	cin >> n;
	rep(t, 0, 2) rep(i, 0, n) {
		cin >> l[t][i]; 
		pii cur; cur.fi = i; cur.se = l[t][i];
		while (tp[t] > 1 && check(h[t][tp[t] - 1], h[t][tp[t]], cur, t)) tp[t] --;
		h[t][++ tp[t]] = cur;
	} 
	rep(t, 0, 2) {
		rep(i, 1, tp[t]) {
			LL x = (h[t][i].se - h[t][i + 1].se) / (h[t][i].fi - h[t][i + 1].fi);
			pos.pb(x); pos.pb(x + 1);
		}
	}
	sort(all(pos));
    pos.resize(unique(pos.begin(), pos.end()) - pos.begin());
    //for (auto x : pos) cout << x  << " ";
	//cout << "\n"; 
    __int128 ans = 0;
    int p0 = tp[0], p1 = 1;
	rep(i, 0, pos.size() - 1) {
		int l = pos[i], r = pos[i + 1] - 1;
		while (p0 > 1 && eval(h[0][p0 - 1], l) >= eval(h[0][p0], l)) p0 --;
		while (p1 < tp[1] && eval(h[1][p1 + 1], l) <= eval(h[1][p1], l)) p1 ++;
		__int128 v1 = eval(h[1][p1], l) - eval(h[0][p0], l) + 1;
		__int128 v2 = eval(h[1][p1], r) - eval(h[0][p0], r) + 1;
		__int128 del = h[0][p0].fi - h[1][p1].fi;
		//cout << l << " " << r << "\n"; 
		//cout << h[0][p0].fi << " " << h[0][p0].se << "\n";
		//cout << h[1][p1].fi << " " << h[1][p1].se << "\n";
		//cout << (int)v1 << " " << (int)v2 << " " << - (int)del << "\n";
		if (del > 0) {
			swap(v1, v2); del = - del;
		}
		LL len = r - l + 1;
		if (v1 <= 0) continue;
		if (v2 < 0) {
			v2 = v1 % (- del);
			len = (v1 - v2) / (-del) + 1;
		}
		//cout << (int)(v1 + v2) * len / 2 << "\n";
		ans += (v1 + v2) * len / 2; ans %= mod; 
	} 
	int res = ans;
	cout << res << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 9568kb

input:

3
5 5 2
7 6 7

output:

6

result:

ok 1 number(s): "6"

Test #2:

score: 0
Accepted
time: 1ms
memory: 9556kb

input:

4
2 3 1 6
5 6 4 8

output:

0

result:

ok 1 number(s): "0"

Test #3:

score: -100
Wrong Answer
time: 52ms
memory: 11424kb

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:

266857399

result:

wrong answer 1st numbers differ - expected: '2000014', found: '266857399'