oj.uz

Submission #814282

# Submission time Handle Problem Language Result Execution time Memory
814282 2023-08-08T06:40:50 Z 이성호(#10121) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 891 ms 974584 KB 
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#define int long long
using namespace std;
using ll = long long;
struct Eq
{
    ll xy, x, y, c;
    Eq()
    {
        xy = x = y = c = 0;
    }
    Eq(ll _xy, ll _x, ll _y, ll _c)
    {
        xy = _xy, x = _x, y = _y, c = _c;
    }
    Eq operator+(Eq e) {
        Eq eq;
        eq.xy = xy + e.xy, eq.x = x + e.x, eq.y = y + e.y, eq.c = c + e.c;
        return eq;
    }
    Eq& operator+=(const Eq& e)
    {
        xy += e.xy; x += e.x; y += e.y; c += e.c;
        return *this;
    }
    ll calc(ll a, ll b)
    {
        return xy * a * b + x * a + y * b + c;
    }
};
struct Node
{
    int l, r;
    Eq val;
    Node()
    {
        l = r = -1;
    }
};
const int inf = 2e9;
struct PDST
{
    Node tree[20000005];
    int pv;
    int root[400005];
    int addNode()
    {
        Node node;
        tree[pv++] = node;
        return pv - 1;
    }
    PDST()
    {
        root[0] = addNode();
    }
    void push(int i)
    {
        root[i] = addNode();
        tree[root[i]] = tree[root[i-1]];
    }
    void update(int node, int s, int e, int id, Eq eq)
    {
        tree[node].val += eq;
        if (s == e) return;
        int m = s + e >> 1;
        if (id <= m) {
            int prev = tree[node].l;
            tree[node].l = addNode();
            if (prev != -1) tree[tree[node].l] = tree[prev];
            update(tree[node].l, s, m, id, eq);
        }
        else {
            int prev = tree[node].r;
            tree[node].r = addNode();
            if (prev != -1) tree[tree[node].r] = tree[prev];
            update(tree[node].r, m+1, e, id, eq);
        }
    }
    Eq query(int node, int s, int e, int l, int r)
    {
        if (e < l || r < s) return {};
        if (l <= s && e <= r) return tree[node].val;
        Eq ret = {};
        int m = s + e >> 1;
        if (tree[node].l != -1) ret += query(tree[node].l, s, m, l, r);
        if (tree[node].r != -1) ret += query(tree[node].r, m+1, e, l, r);
        return ret;
    }
};
PDST seg;
struct Query
{
    int x1, x2;
    int sgn, id;
    int y;
    Query(int _x1, int _x2, int _sgn, int _id, int _y)
    {
        x1 = _x1, x2 = _x2, sgn = _sgn, id = _id, y = _y;
    }
};
struct Update
{
    int x;
    Eq eq;
    int y;
    Update(int _x, Eq _eq, int _y)
    {
        x = _x, eq = _eq, y = _y;
    }
};
int N, Q;
vector<Update> upd[400005], upds;
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int R, C, M; cin >> R >> C >> N >> Q >> M;
    vector<int> cpx;
    for (int i = 0; i < N; i++) {
        ll x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        upds.push_back({x1+1, {1, -y1, -x1, x1*y1}, y1+1});
        upds.push_back({x2+1, {-1, y1, x2, -x2*y1}, y1+1});
        upds.push_back({x1+1, {-1, y2, x1, -x1*y2}, y2+1});
        upds.push_back({x2+1, {1, -y2, -x2, x2*y2}, y2+1});
        cpx.push_back(y1+1); cpx.push_back(y2+1);
    }
    cpx.push_back(0);
    sort(cpx.begin(), cpx.end());
    for (auto p:upds) {
        upd[lower_bound(cpx.begin(), cpx.end(), p.y)-cpx.begin()].push_back(p);
    }
    for (int i = 1; i < (int)cpx.size(); i++) {
        seg.push(i);
        for (auto p:upd[i]) {
            seg.update(seg.root[i], 1, inf, p.x, p.eq);
        }
    }
    __int128_t ans = 0;
    while (Q--) {
        ll x1, y1, x2, y2, v; cin >> x1 >> y1 >> x2 >> y2 >> v;
        x1 = (x1 + ans * v) % M, x2 = (x2 + ans * v) % M, y1 = (y1 + ans * v) % M, y2 = (y2 + ans * v) % M;
        ans = 0;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        int pos = upper_bound(cpx.begin(), cpx.end(), y2) - cpx.begin() - 1;
        ans += seg.query(seg.root[pos], 1, inf, 1, x2).calc(x2, y2);
        if (x1) ans -= seg.query(seg.root[pos], 1, inf, 1, x1).calc(x1, y2);
        int pos2 = upper_bound(cpx.begin(), cpx.end(), y1) - cpx.begin() - 1;
        ans -= seg.query(seg.root[pos2], 1, inf, 1, x2).calc(x2, y1);
        if (x1) ans += seg.query(seg.root[pos2], 1, inf, 1, x1).calc(x1, y1);
        cout << (ll)ans << '\n';
    }
    return 0;
}

Compilation message

Main.cpp: In member function 'void PDST::update(long long int, long long int, long long int, long long int, Eq)':
Main.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |         int m = s + e >> 1;
      |                 ~~^~~
Main.cpp: In member function 'Eq PDST::query(long long int, long long int, long long int, long long int, long long int)':
Main.cpp:87:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int m = s + e >> 1;
      |                 ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 949228 KB Output is correct
2 Correct 335 ms 949224 KB Output is correct
3 Correct 345 ms 949204 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 949228 KB Output is correct
2 Correct 335 ms 949224 KB Output is correct
3 Correct 345 ms 949204 KB Output is correct
4 Correct 381 ms 951256 KB Output is correct
5 Correct 371 ms 951436 KB Output is correct
6 Correct 408 ms 951180 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 949228 KB Output is correct
2 Correct 335 ms 949224 KB Output is correct
3 Correct 345 ms 949204 KB Output is correct
4 Correct 381 ms 951256 KB Output is correct
5 Correct 371 ms 951436 KB Output is correct
6 Correct 408 ms 951180 KB Output is correct
7 Correct 496 ms 971256 KB Output is correct
8 Correct 831 ms 971632 KB Output is correct
9 Correct 651 ms 974108 KB Output is correct
10 Correct 754 ms 971692 KB Output is correct
11 Correct 639 ms 971948 KB Output is correct
12 Correct 626 ms 971672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 949228 KB Output is correct
2 Correct 335 ms 949224 KB Output is correct
3 Correct 345 ms 949204 KB Output is correct
4 Correct 381 ms 951256 KB Output is correct
5 Correct 371 ms 951436 KB Output is correct
6 Correct 408 ms 951180 KB Output is correct
7 Correct 502 ms 971548 KB Output is correct
8 Correct 768 ms 971780 KB Output is correct
9 Correct 570 ms 974232 KB Output is correct
10 Correct 690 ms 972088 KB Output is correct
11 Correct 627 ms 972180 KB Output is correct
12 Correct 585 ms 971964 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 949228 KB Output is correct
2 Correct 335 ms 949224 KB Output is correct
3 Correct 345 ms 949204 KB Output is correct
4 Correct 381 ms 951256 KB Output is correct
5 Correct 371 ms 951436 KB Output is correct
6 Correct 408 ms 951180 KB Output is correct
7 Correct 496 ms 971256 KB Output is correct
8 Correct 831 ms 971632 KB Output is correct
9 Correct 651 ms 974108 KB Output is correct
10 Correct 754 ms 971692 KB Output is correct
11 Correct 639 ms 971948 KB Output is correct
12 Correct 626 ms 971672 KB Output is correct
13 Correct 502 ms 971548 KB Output is correct
14 Correct 768 ms 971780 KB Output is correct
15 Correct 570 ms 974232 KB Output is correct
16 Correct 690 ms 972088 KB Output is correct
17 Correct 627 ms 972180 KB Output is correct
18 Correct 585 ms 971964 KB Output is correct
19 Correct 531 ms 972172 KB Output is correct
20 Correct 786 ms 972084 KB Output is correct
21 Correct 593 ms 974312 KB Output is correct
22 Correct 705 ms 971980 KB Output is correct
23 Correct 625 ms 972288 KB Output is correct
24 Correct 577 ms 972088 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 971220 KB Output is correct
2 Correct 784 ms 971672 KB Output is correct
3 Correct 624 ms 973984 KB Output is correct
4 Correct 743 ms 971744 KB Output is correct
5 Correct 643 ms 971888 KB Output is correct
6 Correct 699 ms 971692 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 971220 KB Output is correct
2 Correct 784 ms 971672 KB Output is correct
3 Correct 624 ms 973984 KB Output is correct
4 Correct 743 ms 971744 KB Output is correct
5 Correct 643 ms 971888 KB Output is correct
6 Correct 699 ms 971692 KB Output is correct
7 Correct 571 ms 971992 KB Output is correct
8 Correct 891 ms 972964 KB Output is correct
9 Correct 726 ms 974584 KB Output is correct
10 Correct 832 ms 972852 KB Output is correct
11 Correct 713 ms 973160 KB Output is correct
12 Correct 640 ms 972984 KB Output is correct