oj.uz

답안 #814263

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
814263 2023-08-08T06:36:58 Z 이성호(#10121) Posters on the wall (CPSPC17_posters) C++17
0 / 100
 366 ms 1048576 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[25000005];
    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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 366 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 326 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 326 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -