oj.uz

답안 #428753

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428753 2021-06-15T14:13:45 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
0 / 100
 872 ms 1048580 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <tuple>
#define pii pair<int, int>
#define tiiii tuple<int, int, int, int>
#define ff first
#define ss second
#define int long long

using namespace std;

int cnt = 1;
struct Node
{
    long long a, b, c, d;
    int l, r;
    Node(void) : a(0), b(0), c(0), d(0), l(-1), r(-1) {}
}seg[25252525];

int upd(int ind, int s, int e, int pos, long long a, long long b, long long c, long long d)
{
    int ret = cnt++;
    if(ind != -1) seg[ret] = seg[ind];
    if(s + 1 == e)
    {
        seg[ret].a += a;
        seg[ret].b += b;
        seg[ret].c += c;
        seg[ret].d += d;
        return ret;
    }

    int mid = s + e >> 1;
    if(pos < mid) seg[ret].l = upd(seg[ret].l, s, mid, pos, a, b, c, d);
    else seg[ret].r = upd(seg[ret].r, mid, e, pos, a, b, c, d);

    seg[ret].a = 0;
    if(seg[ret].l != -1) seg[ret].a += seg[seg[ret].l].a;
    if(seg[ret].r != -1) seg[ret].a += seg[seg[ret].r].a;
    seg[ret].b = 0;
    if(seg[ret].l != -1) seg[ret].b += seg[seg[ret].l].b;
    if(seg[ret].r != -1) seg[ret].b += seg[seg[ret].r].b;
    seg[ret].c = 0;
    if(seg[ret].l != -1) seg[ret].c += seg[seg[ret].l].c;
    if(seg[ret].r != -1) seg[ret].c += seg[seg[ret].r].c;
    seg[ret].d = 0;
    if(seg[ret].l != -1) seg[ret].d += seg[seg[ret].l].d;
    if(seg[ret].r != -1) seg[ret].d += seg[seg[ret].r].d;
    return ret;
}

long long qry(int ind, int s, int e, int l, int r, int x, int y)
{
    if(e <= l || r <= s || ind == -1) return 0;
    if(l <= s && e <= r)
    {
//        cout << seg[ind].a << ' ' << seg[ind].b << ' ' << seg[ind].c << ' ' << seg[ind].d << endl;
        return seg[ind].a * x * y - seg[ind].b * x - seg[ind].c * y + seg[ind].d;
    }
    int mid = s + e >> 1;
    return qry(seg[ind].l, s, mid, l, r, x, y) + qry(seg[ind].r, mid, e, l, r, x, y);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    freopen("in.txt", "r", stdin);

    int r, c, n, T, m; cin >> r >> c >> n >> T >> m; r += 2; c += 2;
    tiiii rec[n];
    vector<int> pr;
    for(int i = 0; i < n; ++i)
    {
        int x1, x2, y1, y2; cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
        rec[i] = {x1, y1, x2, y2};
        pr.push_back(y1);
        pr.push_back(y2);
    }

    sort(pr.begin(), pr.end());
    pr.resize(unique(pr.begin(), pr.end()) - pr.begin());

    c = pr.size();
    vector<pii> ls[c];
    for(auto &[x1, y1, x2, y2] : rec)
    {
        y1 = lower_bound(pr.begin(), pr.end(), y1) - pr.begin();
        y2 = lower_bound(pr.begin(), pr.end(), y2) - pr.begin();
        ls[y1].push_back({x1, 1});
        ls[y1].push_back({x2, -1});
        ls[y2].push_back({x1, -1});
        ls[y2].push_back({x2, 1});
    }

    int root[c + 1]; root[0] = 0;
    for(int y = 0; y < c; ++y)
    {
        root[y + 1] = root[y];
        for(auto [x, t] : ls[y])
            root[y + 1] = upd(root[y + 1], 0, r, x, t, pr[y] * t, x * t, 1ll * x * pr[y] * t);
    }

    long long prv = 0;
    while(T--)
    {
        int x1, x2, y1, y2, v; cin >> x1 >> y1 >> x2 >> y2 >> v;
        x1 = (x1 + prv * v) % m;
        x2 = (x2 + prv * v) % m;
        y1 = (y1 + prv * v) % m;
        y2 = (y2 + prv * v) % m;
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
        int yi1 = lower_bound(pr.begin(), pr.end(), y1) - pr.begin();
        int yi2 = lower_bound(pr.begin(), pr.end(), y2) - pr.begin();
//        cout << qry(root[y2], 0, r, 0, x2, x2, y2) << endl;
        prv = qry(root[yi2], 0, r, 0, x2, x2, y2) - qry(root[yi2], 0, r, 0, x1, x1, y2)
                -qry(root[yi1], 0, r, 0, x2, x2, y1) + qry(root[yi1], 0, r, 0, x1, x1, y1);
        cout << prv << '\n';
    }
}

Compilation message

Main.cpp: In function 'long long int upd(long long int, long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'long long int qry(long long int, long long int, long long int, long long int, long long int, long long int, long long int)':
Main.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 40.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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