oj.uz

Submission #428767

# Submission time Handle Problem Language Result Execution time Memory
428767 2021-06-15T14:20:47 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1148 ms 798852 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 % m * v) % m;
        x2 = (x2 + prv % m * v) % m;
        y1 = (y1 + prv % m * v) % m;
        y2 = (y2 + prv % m * 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 382 ms 790932 KB Output is correct
2 Correct 382 ms 790976 KB Output is correct
3 Correct 379 ms 790928 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 790932 KB Output is correct
2 Correct 382 ms 790976 KB Output is correct
3 Correct 379 ms 790928 KB Output is correct
4 Correct 419 ms 791468 KB Output is correct
5 Correct 405 ms 791436 KB Output is correct
6 Correct 457 ms 791480 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 790932 KB Output is correct
2 Correct 382 ms 790976 KB Output is correct
3 Correct 379 ms 790928 KB Output is correct
4 Correct 419 ms 791468 KB Output is correct
5 Correct 405 ms 791436 KB Output is correct
6 Correct 457 ms 791480 KB Output is correct
7 Correct 588 ms 796168 KB Output is correct
8 Correct 979 ms 797792 KB Output is correct
9 Correct 671 ms 796912 KB Output is correct
10 Correct 873 ms 797604 KB Output is correct
11 Correct 748 ms 796240 KB Output is correct
12 Correct 685 ms 797756 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 790932 KB Output is correct
2 Correct 382 ms 790976 KB Output is correct
3 Correct 379 ms 790928 KB Output is correct
4 Correct 419 ms 791468 KB Output is correct
5 Correct 405 ms 791436 KB Output is correct
6 Correct 457 ms 791480 KB Output is correct
7 Correct 684 ms 795932 KB Output is correct
8 Correct 1148 ms 797656 KB Output is correct
9 Correct 888 ms 796996 KB Output is correct
10 Correct 936 ms 797664 KB Output is correct
11 Correct 861 ms 796304 KB Output is correct
12 Correct 761 ms 797672 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 382 ms 790932 KB Output is correct
2 Correct 382 ms 790976 KB Output is correct
3 Correct 379 ms 790928 KB Output is correct
4 Correct 419 ms 791468 KB Output is correct
5 Correct 405 ms 791436 KB Output is correct
6 Correct 457 ms 791480 KB Output is correct
7 Correct 588 ms 796168 KB Output is correct
8 Correct 979 ms 797792 KB Output is correct
9 Correct 671 ms 796912 KB Output is correct
10 Correct 873 ms 797604 KB Output is correct
11 Correct 748 ms 796240 KB Output is correct
12 Correct 685 ms 797756 KB Output is correct
13 Correct 684 ms 795932 KB Output is correct
14 Correct 1148 ms 797656 KB Output is correct
15 Correct 888 ms 796996 KB Output is correct
16 Correct 936 ms 797664 KB Output is correct
17 Correct 861 ms 796304 KB Output is correct
18 Correct 761 ms 797672 KB Output is correct
19 Correct 734 ms 798196 KB Output is correct
20 Correct 1046 ms 798852 KB Output is correct
21 Correct 731 ms 797124 KB Output is correct
22 Correct 958 ms 798540 KB Output is correct
23 Correct 857 ms 797008 KB Output is correct
24 Correct 745 ms 798760 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 795332 KB Output is correct
2 Correct 902 ms 796924 KB Output is correct
3 Correct 690 ms 796744 KB Output is correct
4 Correct 822 ms 796824 KB Output is correct
5 Correct 712 ms 795928 KB Output is correct
6 Correct 740 ms 796912 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 795332 KB Output is correct
2 Correct 902 ms 796924 KB Output is correct
3 Correct 690 ms 796744 KB Output is correct
4 Correct 822 ms 796824 KB Output is correct
5 Correct 712 ms 795928 KB Output is correct
6 Correct 740 ms 796912 KB Output is correct
7 Correct 725 ms 798204 KB Output is correct
8 Correct 1008 ms 798808 KB Output is correct
9 Correct 783 ms 797040 KB Output is correct
10 Correct 937 ms 798640 KB Output is correct
11 Correct 803 ms 797156 KB Output is correct
12 Correct 751 ms 798800 KB Output is correct