oj.uz

Submission #814271

# Submission time Handle Problem Language Result Execution time Memory
814271 2023-08-08T06:38:22 Z 이성호(#10121) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 789 ms 974068 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);
        }
    }
    ll 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 << 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 324 ms 949196 KB Output is correct
2 Correct 315 ms 949200 KB Output is correct
3 Correct 315 ms 949196 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 949196 KB Output is correct
2 Correct 315 ms 949200 KB Output is correct
3 Correct 315 ms 949196 KB Output is correct
4 Correct 339 ms 951392 KB Output is correct
5 Correct 342 ms 951284 KB Output is correct
6 Correct 333 ms 951156 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 949196 KB Output is correct
2 Correct 315 ms 949200 KB Output is correct
3 Correct 315 ms 949196 KB Output is correct
4 Correct 339 ms 951392 KB Output is correct
5 Correct 342 ms 951284 KB Output is correct
6 Correct 333 ms 951156 KB Output is correct
7 Correct 476 ms 971076 KB Output is correct
8 Correct 789 ms 971416 KB Output is correct
9 Correct 609 ms 973852 KB Output is correct
10 Correct 719 ms 971496 KB Output is correct
11 Correct 665 ms 971752 KB Output is correct
12 Correct 618 ms 971376 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 949196 KB Output is correct
2 Correct 315 ms 949200 KB Output is correct
3 Correct 315 ms 949196 KB Output is correct
4 Correct 339 ms 951392 KB Output is correct
5 Correct 342 ms 951284 KB Output is correct
6 Correct 333 ms 951156 KB Output is correct
7 Correct 496 ms 971320 KB Output is correct
8 Correct 736 ms 971516 KB Output is correct
9 Correct 568 ms 974000 KB Output is correct
10 Correct 732 ms 971600 KB Output is correct
11 Correct 601 ms 971916 KB Output is correct
12 Correct 608 ms 971592 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 949196 KB Output is correct
2 Correct 315 ms 949200 KB Output is correct
3 Correct 315 ms 949196 KB Output is correct
4 Correct 339 ms 951392 KB Output is correct
5 Correct 342 ms 951284 KB Output is correct
6 Correct 333 ms 951156 KB Output is correct
7 Correct 476 ms 971076 KB Output is correct
8 Correct 789 ms 971416 KB Output is correct
9 Correct 609 ms 973852 KB Output is correct
10 Correct 719 ms 971496 KB Output is correct
11 Correct 665 ms 971752 KB Output is correct
12 Correct 618 ms 971376 KB Output is correct
13 Correct 496 ms 971320 KB Output is correct
14 Correct 736 ms 971516 KB Output is correct
15 Correct 568 ms 974000 KB Output is correct
16 Correct 732 ms 971600 KB Output is correct
17 Correct 601 ms 971916 KB Output is correct
18 Correct 608 ms 971592 KB Output is correct
19 Correct 524 ms 971840 KB Output is correct
20 Correct 744 ms 971820 KB Output is correct
21 Correct 562 ms 974068 KB Output is correct
22 Correct 708 ms 971760 KB Output is correct
23 Correct 595 ms 971968 KB Output is correct
24 Correct 568 ms 971760 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 970816 KB Output is correct
2 Correct 779 ms 971400 KB Output is correct
3 Correct 596 ms 973700 KB Output is correct
4 Correct 745 ms 971764 KB Output is correct
5 Correct 696 ms 971672 KB Output is correct
6 Correct 633 ms 971384 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 486 ms 970816 KB Output is correct
2 Correct 779 ms 971400 KB Output is correct
3 Correct 596 ms 973700 KB Output is correct
4 Correct 745 ms 971764 KB Output is correct
5 Correct 696 ms 971672 KB Output is correct
6 Correct 633 ms 971384 KB Output is correct
7 Incorrect 581 ms 971032 KB Output isn't correct
8 Halted 0 ms 0 KB -