oj.uz

Submission #428746

# Submission time Handle Problem Language Result Execution time Memory
428746 2021-06-15T14:11:46 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 1255 ms 996508 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[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);
}

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 586 ms 988636 KB Output is correct
2 Correct 553 ms 988608 KB Output is correct
3 Correct 528 ms 988652 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 988636 KB Output is correct
2 Correct 553 ms 988608 KB Output is correct
3 Correct 528 ms 988652 KB Output is correct
4 Correct 520 ms 989156 KB Output is correct
5 Correct 562 ms 989108 KB Output is correct
6 Correct 509 ms 989176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 988636 KB Output is correct
2 Correct 553 ms 988608 KB Output is correct
3 Correct 528 ms 988652 KB Output is correct
4 Correct 520 ms 989156 KB Output is correct
5 Correct 562 ms 989108 KB Output is correct
6 Correct 509 ms 989176 KB Output is correct
7 Correct 728 ms 993792 KB Output is correct
8 Correct 1137 ms 995488 KB Output is correct
9 Correct 794 ms 994572 KB Output is correct
10 Correct 998 ms 995276 KB Output is correct
11 Correct 886 ms 993872 KB Output is correct
12 Correct 890 ms 995572 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 988636 KB Output is correct
2 Correct 553 ms 988608 KB Output is correct
3 Correct 528 ms 988652 KB Output is correct
4 Correct 520 ms 989156 KB Output is correct
5 Correct 562 ms 989108 KB Output is correct
6 Correct 509 ms 989176 KB Output is correct
7 Correct 893 ms 993688 KB Output is correct
8 Correct 1255 ms 995460 KB Output is correct
9 Correct 888 ms 994588 KB Output is correct
10 Correct 1089 ms 995276 KB Output is correct
11 Correct 1031 ms 994124 KB Output is correct
12 Correct 881 ms 995396 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 586 ms 988636 KB Output is correct
2 Correct 553 ms 988608 KB Output is correct
3 Correct 528 ms 988652 KB Output is correct
4 Correct 520 ms 989156 KB Output is correct
5 Correct 562 ms 989108 KB Output is correct
6 Correct 509 ms 989176 KB Output is correct
7 Correct 728 ms 993792 KB Output is correct
8 Correct 1137 ms 995488 KB Output is correct
9 Correct 794 ms 994572 KB Output is correct
10 Correct 998 ms 995276 KB Output is correct
11 Correct 886 ms 993872 KB Output is correct
12 Correct 890 ms 995572 KB Output is correct
13 Correct 893 ms 993688 KB Output is correct
14 Correct 1255 ms 995460 KB Output is correct
15 Correct 888 ms 994588 KB Output is correct
16 Correct 1089 ms 995276 KB Output is correct
17 Correct 1031 ms 994124 KB Output is correct
18 Correct 881 ms 995396 KB Output is correct
19 Correct 833 ms 995828 KB Output is correct
20 Correct 1178 ms 996508 KB Output is correct
21 Correct 918 ms 994700 KB Output is correct
22 Correct 1190 ms 996268 KB Output is correct
23 Correct 953 ms 994628 KB Output is correct
24 Correct 970 ms 996464 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 992984 KB Output is correct
2 Correct 1165 ms 994552 KB Output is correct
3 Correct 926 ms 994460 KB Output is correct
4 Correct 1060 ms 994584 KB Output is correct
5 Correct 982 ms 993652 KB Output is correct
6 Correct 925 ms 994612 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 732 ms 992984 KB Output is correct
2 Correct 1165 ms 994552 KB Output is correct
3 Correct 926 ms 994460 KB Output is correct
4 Correct 1060 ms 994584 KB Output is correct
5 Correct 982 ms 993652 KB Output is correct
6 Correct 925 ms 994612 KB Output is correct
7 Incorrect 1024 ms 995092 KB Output isn't correct
8 Halted 0 ms 0 KB -