QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#574438#3938. Gameworld TornadoLaVuna47AC ✓219ms33828kbC++1710.6kb2024-09-18 22:07:052024-09-18 22:07:08

Judging History

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

  • [2024-09-18 22:07:08]
  • 评测
  • 测评结果:AC
  • 用时:219ms
  • 内存:33828kb
  • [2024-09-18 22:07:05]
  • 提交

answer

/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1

#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>

#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1

#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder

#endif  // ATCODER_INTERNAL_BITOP_HPP


namespace atcoder {

#if __cplusplus >= 201703L

template <class S,
          auto op,
          auto e,
          class F,
          auto mapping,
          auto composition,
          auto id>
struct lazy_segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");
    static_assert(
        std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
        "mapping must work as S(F, S)");
    static_assert(
        std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
        "composition must work as F(F, F)");
    static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
                  "id must work as F()");

#else

template <class S,
          S (*op)(S, S),
          S (*e)(),
          class F,
          S (*mapping)(F, S),
          F (*composition)(F, F),
          F (*id)()>
struct lazy_segtree {

#endif

  public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        lz = std::vector<F>(size, id());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        return d[p];
    }

    S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return e();

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        S sml = e(), smr = e();
        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }

        return op(sml, smr);
    }

    S all_prod() { return d[1]; }

    void apply(int p, F f) {
        assert(0 <= p && p < _n);
        p += size;
        for (int i = log; i >= 1; i--) push(p >> i);
        d[p] = mapping(f, d[p]);
        for (int i = 1; i <= log; i++) update(p >> i);
    }
    void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        if (l == r) return;

        l += size;
        r += size;

        for (int i = log; i >= 1; i--) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        {
            int l2 = l, r2 = r;
            while (l < r) {
                if (l & 1) all_apply(l++, f);
                if (r & 1) all_apply(--r, f);
                l >>= 1;
                r >>= 1;
            }
            l = l2;
            r = r2;
        }

        for (int i = 1; i <= log; i++) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    template <bool (*g)(S)> int max_right(int l) {
        return max_right(l, [](S x) { return g(x); });
    }
    template <class G> int max_right(int l, G g) {
        assert(0 <= l && l <= _n);
        assert(g(e()));
        if (l == _n) return _n;
        l += size;
        for (int i = log; i >= 1; i--) push(l >> i);
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!g(op(sm, d[l]))) {
                while (l < size) {
                    push(l);
                    l = (2 * l);
                    if (g(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*g)(S)> int min_left(int r) {
        return min_left(r, [](S x) { return g(x); });
    }
    template <class G> int min_left(int r, G g) {
        assert(0 <= r && r <= _n);
        assert(g(e()));
        if (r == 0) return 0;
        r += size;
        for (int i = log; i >= 1; i--) push((r - 1) >> i);
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!g(op(d[r], sm))) {
                while (r < size) {
                    push(r);
                    r = (2 * r + 1);
                    if (g(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;
    std::vector<F> lz;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
    void all_apply(int k, F f) {
        d[k] = mapping(f, d[k]);
        if (k < size) lz[k] = composition(f, lz[k]);
    }
    void push(int k) {
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = id();
    }
};

}  // namespace atcoder

#endif  // ATCODER_LAZYSEGTREE_HPP


#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define RFOR(i, n) for(int i = n-1; i >= 0; --i)
#define output_vec(vec) { FOR(i_, sz(vec)) cout << vec[i_] << ' '; cout << '\n'; }
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<bool> vb;
typedef short si;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

// addition on interval / min operation
struct S
{
    ll min_val;
    ll sum_val;
};
using F = ll;

const ll INF = 1e18;

S op(S a, S b)
{
    if(a.min_val < b.min_val)
        return a;
    else if(a.min_val > b.min_val)
        return b;
    else
        return {a.min_val, a.sum_val + b.sum_val};
}
S e()
{ 
    return {INF, 0ll};
}
// f(g(x))
S mapping(F f, S x)
{
    return {f+x.min_val, x.sum_val};
}

F composition(F f, F g)
{
    return f+g;
}

F id(){ return 0ll; }


struct Rectangle
{
    pll p1, p2;
};

struct Event
{
    ll x;
    bool begin;
    int rect_id;
};

int solve()
{
    int n;
    if(!(cin >> n))
        return 1;
    vector<Rectangle> a(n);
    FOR(i, n) cin >> a[i].p1.x >> a[i].p1.y >> a[i].p2.x >> a[i].p2.y;
    vector<ll> arr;
    { // linear mapping
        set<ll> ss;
        FOR(i, n) ss.insert(a[i].p1.y), ss.insert(a[i].p2.y);
        unordered_map<ll, ll> I;
        int ctr = 0;
        for(auto item: ss)
            I[item] = ctr++;
        vector<ll> vec{all(ss)};
        FOR(i, sz(vec)-1)
        {
            arr.pb(vec[i+1]-vec[i]);
        }
        FOR(i, n) a[i].p1.y = I[a[i].p1.y], a[i].p2.y = I[a[i].p2.y];
    }
    ll sum_arr = accumulate(all(arr), 0ll);

    // preparing events
    vector<Event> events;
    FOR(i, n)
    {
        events.pb(Event{a[i].p1.x, true, i});
        events.pb(Event{a[i].p2.x, false, i});
    }
    sort(all(events), [](const Event& e1, const Event& e2) -> bool {
        if(e1.x == e2.x)
        {
            return (int)e1.begin < (int)e2.begin;
        }
        return e1.x < e2.x;
    });

    // preparing segment tree
    int N = sz(arr);
    std::vector<S> v(N+10, {0, 0});
    FOR(i, N) v[i] = {0, arr[i]};
    atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
    ll pr_x = events[0].x;
    ll res = 0;
    for(auto [x, begin, rect_id]: events)
    {
        ll dx = x-pr_x;
        res += dx * (sum_arr-seg.all_prod().sum_val);
        if(begin)
        {
            seg.apply(a[rect_id].p1.y, a[rect_id].p2.y, 1);
        }
        else 
        {
            seg.apply(a[rect_id].p1.y, a[rect_id].p2.y, -1);
        }
        pr_x = x;
    }
    cout << res << '\n';
    return 0;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TET = 1e9;
    //cin >> TET;
    for (int i = 1; i <= TET; i++)
    {
        if (solve())
        {
            break;
        }
#ifdef ONPC
        cout << "__________________________" << endl;
#endif
    }
#ifdef ONPC
    cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
2 2 4 4
3 3 5 5

output:

7

result:

ok single line: '7'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

50
0 0 10 3
12 0 22 3
24 0 34 3
36 0 46 3
48 0 58 3
60 0 70 3
72 0 82 3
84 0 94 3
96 0 106 3
108 0 118 3
120 0 130 3
132 0 142 3
144 0 154 3
156 0 166 3
168 0 178 3
180 0 190 3
192 0 202 3
204 0 214 3
216 0 226 3
228 0 238 3
240 0 250 3
252 0 262 3
264 0 274 3
276 0 286 3
288 0 298 3
300 0 310 3
312...

output:

1500

result:

ok single line: '1500'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

50
0 0 30 3
0 5 30 8
0 10 30 13
0 15 30 18
0 20 30 23
0 25 30 28
0 30 30 33
0 35 30 38
0 40 30 43
0 45 30 48
0 50 30 53
0 55 30 58
0 60 30 63
0 65 30 68
0 70 30 73
0 75 30 78
0 80 30 83
0 85 30 88
0 90 30 93
0 95 30 98
0 100 30 103
0 105 30 108
0 110 30 113
0 115 30 118
0 120 30 123
0 125 30 128
0 1...

output:

4500

result:

ok single line: '4500'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

100
0 0 6 6
3 3 9 9
6 6 12 12
9 9 15 15
12 12 18 18
15 15 21 21
18 18 24 24
21 21 27 27
24 24 30 30
27 27 33 33
30 30 36 36
33 33 39 39
36 36 42 42
39 39 45 45
42 42 48 48
45 45 51 51
48 48 54 54
51 51 57 57
54 54 60 60
57 57 63 63
60 60 66 66
63 63 69 69
66 66 72 72
69 69 75 75
72 72 78 78
75 75 81...

output:

2709

result:

ok single line: '2709'

Test #5:

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

input:

999
0 0 6 6
3 3 9 9
6 6 12 12
9 9 15 15
12 12 18 18
15 15 21 21
18 18 24 24
21 21 27 27
24 24 30 30
27 27 33 33
30 30 36 36
33 33 39 39
36 36 42 42
39 39 45 45
42 42 48 48
45 45 51 51
48 48 54 54
51 51 57 57
54 54 60 60
57 57 63 63
60 60 66 66
63 63 69 69
66 66 72 72
69 69 75 75
72 72 78 78
75 75 81...

output:

26982

result:

ok single line: '26982'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

100
0 0 4 2
2 0 6 2
4 0 8 2
6 0 10 2
8 0 12 2
10 0 14 2
12 0 16 2
14 0 18 2
16 0 20 2
18 0 22 2
20 0 24 2
22 0 26 2
24 0 28 2
26 0 30 2
28 0 32 2
30 0 34 2
32 0 36 2
34 0 38 2
36 0 40 2
38 0 42 2
40 0 44 2
42 0 46 2
44 0 48 2
46 0 50 2
48 0 52 2
50 0 54 2
52 0 56 2
54 0 58 2
56 0 60 2
58 0 62 2
60 0...

output:

404

result:

ok single line: '404'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3612kb

input:

100
0 0 4 2
0 2 4 4
0 4 4 6
0 6 4 8
0 8 4 10
0 10 4 12
0 12 4 14
0 14 4 16
0 16 4 18
0 18 4 20
0 20 4 22
0 22 4 24
0 24 4 26
0 26 4 28
0 28 4 30
0 30 4 32
0 32 4 34
0 34 4 36
0 36 4 38
0 38 4 40
0 40 4 42
0 42 4 44
0 44 4 46
0 46 4 48
0 48 4 50
0 50 4 52
0 52 4 54
0 54 4 56
0 56 4 58
0 58 4 60
0 60 ...

output:

800

result:

ok single line: '800'

Test #8:

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

input:

400
0 0 3000 2
0 4 3000 6
0 8 3000 10
0 12 3000 14
0 16 3000 18
0 20 3000 22
0 24 3000 26
0 28 3000 30
0 32 3000 34
0 36 3000 38
0 40 3000 42
0 44 3000 46
0 48 3000 50
0 52 3000 54
0 56 3000 58
0 60 3000 62
0 64 3000 66
0 68 3000 70
0 72 3000 74
0 76 3000 78
0 80 3000 82
0 84 3000 86
0 88 3000 90
0 ...

output:

2240000

result:

ok single line: '2240000'

Test #9:

score: 0
Accepted
time: 144ms
memory: 33828kb

input:

100000
0 1000000 200000 1000001
1 999999 199999 1000002
2 999998 199998 1000003
3 999997 199997 1000004
4 999996 199996 1000005
5 999995 199995 1000006
6 999994 199994 1000007
7 999993 199993 1000008
8 999992 199992 1000009
9 999991 199991 1000010
10 999990 199990 1000011
11 999989 199989 1000012
12...

output:

20000000000

result:

ok single line: '20000000000'

Test #10:

score: 0
Accepted
time: 97ms
memory: 20160kb

input:

100000
0 0 1000000000 19602
0 20000 1000000000 33235
0 40000 1000000000 56866
0 60000 1000000000 62652
0 80000 1000000000 85686
0 100000 1000000000 119548
0 120000 1000000000 121383
0 140000 1000000000 142985
0 160000 1000000000 166477
0 180000 1000000000 180907
0 200000 1000000000 213625
0 220000 1...

output:

750856076996563747

result:

ok single line: '750856076996563747'

Test #11:

score: 0
Accepted
time: 219ms
memory: 33708kb

input:

100000
804289383 681692777 846930886 714636915
424238335 649760492 957747793 719885386
189641421 25202362 596516649 350490027
102520059 44897763 783368690 967513926
365180540 303455736 540383426 304089172
35005211 294702567 521595368 726956429
336465782 233665123 861021530 278722862
145174067 101513...

output:

999907590278919117

result:

ok single line: '999907590278919117'

Test #12:

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

input:

1000
0 0 1 1000
2 0 3 1000
4 0 5 1000
6 0 7 1000
8 0 9 1000
10 0 11 1000
12 0 13 1000
14 0 15 1000
16 0 17 1000
18 0 19 1000
20 0 21 1000
22 0 23 1000
24 0 25 1000
26 0 27 1000
28 0 29 1000
30 0 31 1000
32 0 33 1000
34 0 35 1000
36 0 37 1000
38 0 39 1000
40 0 41 1000
42 0 43 1000
44 0 45 1000
46 0 4...

output:

750000

result:

ok single line: '750000'