oj.uz

Submission #428718

# Submission time Handle Problem Language Result Execution time Memory
428718 2021-06-15T14:03:01 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 1184 ms 798772 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

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[20202020];

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);
}

int 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 'int upd(int, int, int, int, long long int, long long int, long long int, long long int)':
Main.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'long long int qry(int, int, int, int, int, int, int)':
Main.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 790976 KB Output is correct
2 Correct 400 ms 790912 KB Output is correct
3 Correct 392 ms 790964 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 790976 KB Output is correct
2 Correct 400 ms 790912 KB Output is correct
3 Correct 392 ms 790964 KB Output is correct
4 Correct 408 ms 791424 KB Output is correct
5 Correct 403 ms 791416 KB Output is correct
6 Correct 393 ms 791496 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 790976 KB Output is correct
2 Correct 400 ms 790912 KB Output is correct
3 Correct 392 ms 790964 KB Output is correct
4 Correct 408 ms 791424 KB Output is correct
5 Correct 403 ms 791416 KB Output is correct
6 Correct 393 ms 791496 KB Output is correct
7 Correct 596 ms 796100 KB Output is correct
8 Correct 942 ms 797936 KB Output is correct
9 Correct 696 ms 796776 KB Output is correct
10 Correct 888 ms 797648 KB Output is correct
11 Correct 888 ms 796236 KB Output is correct
12 Correct 805 ms 798028 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 790976 KB Output is correct
2 Correct 400 ms 790912 KB Output is correct
3 Correct 392 ms 790964 KB Output is correct
4 Correct 408 ms 791424 KB Output is correct
5 Correct 403 ms 791416 KB Output is correct
6 Correct 393 ms 791496 KB Output is correct
7 Correct 705 ms 796100 KB Output is correct
8 Correct 993 ms 797904 KB Output is correct
9 Correct 751 ms 797056 KB Output is correct
10 Correct 906 ms 797548 KB Output is correct
11 Correct 850 ms 796316 KB Output is correct
12 Correct 750 ms 797764 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 410 ms 790976 KB Output is correct
2 Correct 400 ms 790912 KB Output is correct
3 Correct 392 ms 790964 KB Output is correct
4 Correct 408 ms 791424 KB Output is correct
5 Correct 403 ms 791416 KB Output is correct
6 Correct 393 ms 791496 KB Output is correct
7 Correct 596 ms 796100 KB Output is correct
8 Correct 942 ms 797936 KB Output is correct
9 Correct 696 ms 796776 KB Output is correct
10 Correct 888 ms 797648 KB Output is correct
11 Correct 888 ms 796236 KB Output is correct
12 Correct 805 ms 798028 KB Output is correct
13 Correct 705 ms 796100 KB Output is correct
14 Correct 993 ms 797904 KB Output is correct
15 Correct 751 ms 797056 KB Output is correct
16 Correct 906 ms 797548 KB Output is correct
17 Correct 850 ms 796316 KB Output is correct
18 Correct 750 ms 797764 KB Output is correct
19 Correct 767 ms 798316 KB Output is correct
20 Correct 1184 ms 798772 KB Output is correct
21 Correct 926 ms 797068 KB Output is correct
22 Correct 1078 ms 798500 KB Output is correct
23 Correct 1042 ms 797000 KB Output is correct
24 Correct 858 ms 798772 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 795256 KB Output is correct
2 Correct 1066 ms 796880 KB Output is correct
3 Correct 757 ms 796780 KB Output is correct
4 Correct 996 ms 796896 KB Output is correct
5 Correct 847 ms 796008 KB Output is correct
6 Correct 775 ms 796856 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 795256 KB Output is correct
2 Correct 1066 ms 796880 KB Output is correct
3 Correct 757 ms 796780 KB Output is correct
4 Correct 996 ms 796896 KB Output is correct
5 Correct 847 ms 796008 KB Output is correct
6 Correct 775 ms 796856 KB Output is correct
7 Incorrect 873 ms 797412 KB Output isn't correct
8 Halted 0 ms 0 KB -