QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#550953#9242. An Easy Geometry Problemucup-team004#TL 67ms3968kbC++208.6kb2024-09-07 14:49:572024-09-07 14:49:57

Judging History

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

  • [2024-09-07 14:49:57]
  • 评测
  • 测评结果：TL
  • 用时：67ms
  • 内存：3968kb
查看
  • [2024-09-07 14:49:57]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
// TODO: Dynamic ModInt

template<typename T>
constexpr T power(T a, u64 b) {
    T res {1};
    for (; b != 0; b /= 2, a *= a) {
        if (b % 2 == 1) {
            res *= a;
        }
    }
    return res;
}

template<u32 P>
constexpr u32 mulMod(u32 a, u32 b) {
    return 1ULL * a * b % P;
}

template<u64 P>
constexpr u64 mulMod(u64 a, u64 b) {
    u64 res = a * b - u64(1.L * a * b / P - 0.5L) * P;
    res %= P;
    return res;
}

template<typename U, U P>
requires std::unsigned_integral<U>
struct ModIntBase {
public:
    constexpr ModIntBase() : x {0} {}
    
    template<typename T>
    requires std::integral<T>
    constexpr ModIntBase(T x_) : x {norm(x_ % T {P})} {}
    
    constexpr static U norm(U x) {
        if ((x >> (8 * sizeof(U) - 1) & 1) == 1) {
            x += P;
        }
        if (x >= P) {
            x -= P;
        }
        return x;
    }
    
    constexpr U val() const {
        return x;
    }
    
    constexpr ModIntBase operator-() const {
        ModIntBase res;
        res.x = norm(P - x);
        return res;
    }
    
    constexpr ModIntBase inv() const {
        return power(*this, P - 2);
    }
    
    constexpr ModIntBase &operator*=(const ModIntBase &rhs) & {
        x = mulMod<P>(x, rhs.val());
        return *this;
    }
    
    constexpr ModIntBase &operator+=(const ModIntBase &rhs) & {
        x = norm(x + rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator-=(const ModIntBase &rhs) & {
        x = norm(x - rhs.x);
        return *this;
    }
    
    constexpr ModIntBase &operator/=(const ModIntBase &rhs) & {
        return *this *= rhs.inv();
    }
    
    friend constexpr ModIntBase operator*(ModIntBase lhs, const ModIntBase &rhs) {
        lhs *= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator+(ModIntBase lhs, const ModIntBase &rhs) {
        lhs += rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator-(ModIntBase lhs, const ModIntBase &rhs) {
        lhs -= rhs;
        return lhs;
    }
    
    friend constexpr ModIntBase operator/(ModIntBase lhs, const ModIntBase &rhs) {
        lhs /= rhs;
        return lhs;
    }
    
    friend constexpr std::ostream &operator<<(std::ostream &os, const ModIntBase &a) {
        return os << a.val();
    }
    
    friend constexpr bool operator==(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() == rhs.val();
    }
    
    friend constexpr bool operator!=(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() != rhs.val();
    }
    
    friend constexpr bool operator<(ModIntBase lhs, ModIntBase rhs) {
        return lhs.val() < rhs.val();
    }
    
private:
    U x;
};

template<u32 P>
using ModInt = ModIntBase<u32, P>;

template<u64 P>
using ModInt64 = ModIntBase<u64, P>;

constexpr u64 P = u64(1E18) + 9;
using Z = ModInt64<P>;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
};

constexpr Z B = 1145141ULL;

struct Tag {
    Z add = 0ULL;
    
    void apply(const Tag &t) & {
        add += t.add;
    }
};

struct Info {
    Z s1 = 0ULL;
    Z s2 = 0ULL;
    Z c = 0ULL;
    Z p = 1ULL;
    
    void apply(const Tag &t) & {
        s1 += c * t.add;
        s2 += c * t.add;
    }
};

Info operator+(const Info &a, const Info &b) {
    Info c;
    c.s1 = a.s1 * b.p + b.s1;
    c.s2 = a.s2 + a.p * b.s2;
    c.c = a.c * b.p + b.c;
    c.p = a.p * b.p;
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, q, k, b;
    std::cin >> n >> q >> k >> b;
    
    std::vector<int> A(n);
    for (int i = 0; i < n; i++) {
        std::cin >> A[i];
        A[i] = 2 * A[i] - k * i;
    }
    b *= 2;
    
    LazySegmentTree<Info, Tag> seg(n);
    for (int i = 0; i < n; i++) {
        seg.modify(i, {i64(A[i]), i64(A[i]), 1ULL, B});
    }
    
    while (q--) {
        int o;
        std::cin >> o;
        if (o == 1) {
            int l, r, v;
            std::cin >> l >> r >> v;
            l--;
            seg.rangeApply(l, r, {i64(2 * v)});
        } else {
            int i;
            std::cin >> i;
            i--;
            
            int lo = 0, hi = std::min(i, n - 1 - i);
            while (lo < hi) {
                int r = (lo + hi + 1) / 2;
                auto al = seg.rangeQuery(i - r, i);
                auto ar = seg.rangeQuery(i + 1, i + 1 + r);
                if (al.s1 + al.c * i64(b) == ar.s2) {
                    lo = r;
                } else {
                    hi = r - 1;
                }
            }
            std::cout << lo << "\n";
        }
    }
    
    return 0;
}
源文件, 语言: C++20

详细

Test #1:

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

input:

6 6 6 2
1 5 9 10 15 18
2 2
1 3 3 -3
2 2
1 3 4 3
2 3
2 4

output:

1
0
2
0

result:

ok 4 number(s): "1 0 2 0"

Test #2:

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

input:

5000 5000 2 0
-329 -328 -327 -326 -325 -324 -323 -322 -321 -320 -319 -318 -317 -316 -315 -314 -313 -312 -311 -310 -309 -308 -307 -306 -305 -304 -303 -302 -301 -300 -299 -298 -297 -296 -295 -294 -293 -292 -291 -290 -289 -288 -287 -286 -285 -284 -283 -282 -281 -280 -279 -278 -277 -276 -275 -274 -273 -...

output:

2
304
73
29
61
292
139
48
17
99
6
5
53
93
3
91
65
29
33
306
21
24
17
21
281
12
16
1
33
7
18
96
7
40
39
13
7
46
43
16
1
72
33
16
22
5
6
189
27
1
35
107
43
34
3
27
20
21
44
56
96
36
2
27
22
30
32
6
5
105
27
37
12
58
2
21
154
17
110
57
3
7
33
15
24
94
68
25
1
14
10
4
10
2
25
39
36
33
164
11
19
181
11
3...

result:

ok 3337 numbers

Test #3:

score: 0
Accepted
time: 61ms
memory: 3916kb

input:

5000 5000 2 0
793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 86...

output:

362
82
14
234
140
5
44
136
22
43
29
96
59
23
25
61
193
22
39
39
23
53
48
76
100
58
120
24
12
106
32
48
73
63
116
16
136
10
28
15
84
30
65
1
54
15
16
70
1
95
74
14
17
20
36
254
22
29
70
172
106
2
25
8
98
35
169
16
2
2
99
10
36
40
3
69
272
170
219
12
79
26
78
100
10
167
140
70
34
17
23
21
55
10
6
17
6...

result:

ok 3313 numbers

Test #4:

score: 0
Accepted
time: 66ms
memory: 3968kb

input:

5000 5000 2 0
-456 -455 -454 -453 -452 -451 -450 -449 -448 -447 -446 -445 -444 -443 -442 -441 -440 -439 -438 -437 -436 -435 -434 -433 -432 -431 -430 -429 -428 -427 -426 -425 -424 -423 -422 -421 -420 -419 -418 -417 -416 -415 -414 -413 -412 -411 -410 -409 -408 -407 -406 -405 -404 -403 -402 -401 -400 -...

output:

8
75
80
408
385
73
37
402
338
43
11
163
3
7
80
0
339
47
384
8
10
47
162
307
30
28
36
14
27
126
271
151
4
11
11
9
92
154
2
15
28
160
205
12
59
79
114
23
22
141
7
12
31
42
120
0
34
2
167
157
76
32
20
298
47
104
76
33
49
34
1
40
16
1
28
7
4
55
14
8
68
17
7
117
1
14
14
80
44
8
45
49
65
15
49
56
50
40
14...

result:

ok 3296 numbers

Test #5:

score: -100
Time Limit Exceeded

input:

200000 199999 -195 -119
-267 -146 191 -456 835 265 -226 -264 160 -101 739 -988 -967 890 -753 -854 514 491 -733 662 681 -362 804 -714 -1000 -790 931 -450 212 94 239 638 400 -167 -360 18 606 256 445 695 -509 643 -892 213 -32 42 400 733 -667 -986 225 493 -699 547 409 -35 394 920 -163 -908 -576 921 -997...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:
English 繁體中文 简体中文

服务器时间: 2024-12-02 18:04:43 | 开源项目