oj.uz

Submission #423391

# Submission time Handle Problem Language Result Execution time Memory
423391 2021-06-11T04:54:51 Z 최서현(#7497) Crossing (JOI21_crossing) C++17
0 / 100
 0 ms 204 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define tiii tuple<int, int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
#define DEBUG
const int Q = (int)1e9 + 7;
const int Q2 = 500'000'004;

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    pii A[n]; for(auto &i : A) cin >> i.ff >> i.ss;
    sort(A, A + n);

    if(n == 1) { cout << 0; return 0; }

    int X[n - 1], Y1[n - 1], Y2[n - 1];
    for(int i = 0; i < n; ++i) X[i] = A[i + 1].ff - A[i].ff;
    Y1[n - 2] = A[n - 1].ss; for(int i = n - 3; i >= 0; --i) Y1[i] = max(Y1[i + 1], A[i + 1].ss);
    Y2[0] = A[0].ss; for(int i = 1; i < n - 1; ++i) Y2[i] = min(Y2[i - 1], A[i].ss);

    int a = 0, b = 0, c = 0, pt = 0, ans = 0;
    for(int i = 0; i < n - 1; ++i) if(Y1[i] > Y2[i]) ans = (ans + 1ll * X[i] * (X[i] + 1) % Q * Q2 % Q * (Y1[i] - Y2[i]) % Q * (Y1[i] - Y2[i] + 1) % Q * Q2 % Q) % Q;
    for(int i = 0; i < n - 1; ++i)
    {
        while(pt < n - 1 && Y1[pt] >= Y2[i])
        {
            a = (a + X[pt]) % Q;
            b = (Q + b - 1ll * X[pt] * (2 * Y1[pt] + 1) % Q) % Q;
            c = (c + 1ll * X[pt] * ((1ll * Y1[pt] * Y1[pt] + Y1[pt]) % Q) % Q) % Q;
            ++pt;
        }
        if(pt == i)
        {
            ++pt;
        }
        else
        {
            a = (Q + a - X[i]) % Q;
            b = (b + 1ll * X[i] * (2 * Y1[i] + 1) % Q) % Q;
            c = (Q + c - 1ll * X[i] * ((1ll * Y1[i] * Y1[i] + Y1[i]) % Q) % Q) % Q;
        }
        ans = (ans + (1ll * a * Y2[i] % Q * Y2[i] % Q + 1ll * b * Y2[i] % Q + c) % Q * X[i] % Q * Q2 % Q) % Q;
    }

    cout << ans;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -