oj.uz

Submission #814249

# Submission time Handle Problem Language Result Execution time Memory
814249 2023-08-08T06:34:33 Z 이성호(#10121) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 778 ms 735200 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 = 1e9 + 10;
struct PDST
{
    Node tree[15000005];
    int pv;
    int root[200005];
    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[200005], 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 274 ms 709636 KB Output is correct
2 Correct 256 ms 709692 KB Output is correct
3 Correct 245 ms 709636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 709636 KB Output is correct
2 Correct 256 ms 709692 KB Output is correct
3 Correct 245 ms 709636 KB Output is correct
4 Correct 276 ms 711868 KB Output is correct
5 Correct 263 ms 712004 KB Output is correct
6 Correct 257 ms 711784 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 709636 KB Output is correct
2 Correct 256 ms 709692 KB Output is correct
3 Correct 245 ms 709636 KB Output is correct
4 Correct 276 ms 711868 KB Output is correct
5 Correct 263 ms 712004 KB Output is correct
6 Correct 257 ms 711784 KB Output is correct
7 Correct 422 ms 732168 KB Output is correct
8 Correct 738 ms 732476 KB Output is correct
9 Correct 525 ms 734980 KB Output is correct
10 Correct 684 ms 732612 KB Output is correct
11 Correct 619 ms 732852 KB Output is correct
12 Correct 634 ms 732516 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 709636 KB Output is correct
2 Correct 256 ms 709692 KB Output is correct
3 Correct 245 ms 709636 KB Output is correct
4 Correct 276 ms 711868 KB Output is correct
5 Correct 263 ms 712004 KB Output is correct
6 Correct 257 ms 711784 KB Output is correct
7 Correct 430 ms 732464 KB Output is correct
8 Correct 713 ms 732620 KB Output is correct
9 Correct 506 ms 735068 KB Output is correct
10 Correct 675 ms 732764 KB Output is correct
11 Correct 572 ms 732988 KB Output is correct
12 Correct 553 ms 732612 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 709636 KB Output is correct
2 Correct 256 ms 709692 KB Output is correct
3 Correct 245 ms 709636 KB Output is correct
4 Correct 276 ms 711868 KB Output is correct
5 Correct 263 ms 712004 KB Output is correct
6 Correct 257 ms 711784 KB Output is correct
7 Correct 422 ms 732168 KB Output is correct
8 Correct 738 ms 732476 KB Output is correct
9 Correct 525 ms 734980 KB Output is correct
10 Correct 684 ms 732612 KB Output is correct
11 Correct 619 ms 732852 KB Output is correct
12 Correct 634 ms 732516 KB Output is correct
13 Correct 430 ms 732464 KB Output is correct
14 Correct 713 ms 732620 KB Output is correct
15 Correct 506 ms 735068 KB Output is correct
16 Correct 675 ms 732764 KB Output is correct
17 Correct 572 ms 732988 KB Output is correct
18 Correct 553 ms 732612 KB Output is correct
19 Correct 512 ms 732936 KB Output is correct
20 Correct 778 ms 732912 KB Output is correct
21 Correct 518 ms 735200 KB Output is correct
22 Correct 648 ms 732844 KB Output is correct
23 Correct 565 ms 733036 KB Output is correct
24 Correct 574 ms 732884 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 732280 KB Output is correct
2 Correct 702 ms 732328 KB Output is correct
3 Correct 545 ms 734512 KB Output is correct
4 Correct 678 ms 732356 KB Output is correct
5 Correct 680 ms 732528 KB Output is correct
6 Correct 577 ms 732320 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 732280 KB Output is correct
2 Correct 702 ms 732328 KB Output is correct
3 Correct 545 ms 734512 KB Output is correct
4 Correct 678 ms 732356 KB Output is correct
5 Correct 680 ms 732528 KB Output is correct
6 Correct 577 ms 732320 KB Output is correct
7 Incorrect 553 ms 731816 KB Output isn't correct
8 Halted 0 ms 0 KB -