oj.uz

Submission #428754

# Submission time Handle Problem Language Result Execution time Memory
428754 2021-06-15T14:15:00 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
90 / 100
 966 ms 485632 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[10101010];

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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 474708 KB Output is correct
2 Correct 241 ms 474840 KB Output is correct
3 Correct 224 ms 474764 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 474708 KB Output is correct
2 Correct 241 ms 474840 KB Output is correct
3 Correct 224 ms 474764 KB Output is correct
4 Correct 244 ms 475476 KB Output is correct
5 Correct 259 ms 475604 KB Output is correct
6 Correct 237 ms 475504 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 474708 KB Output is correct
2 Correct 241 ms 474840 KB Output is correct
3 Correct 224 ms 474764 KB Output is correct
4 Correct 244 ms 475476 KB Output is correct
5 Correct 259 ms 475604 KB Output is correct
6 Correct 237 ms 475504 KB Output is correct
7 Correct 476 ms 482904 KB Output is correct
8 Correct 798 ms 484684 KB Output is correct
9 Correct 529 ms 483996 KB Output is correct
10 Correct 739 ms 484352 KB Output is correct
11 Correct 606 ms 483092 KB Output is correct
12 Correct 573 ms 484700 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 474708 KB Output is correct
2 Correct 241 ms 474840 KB Output is correct
3 Correct 224 ms 474764 KB Output is correct
4 Correct 244 ms 475476 KB Output is correct
5 Correct 259 ms 475604 KB Output is correct
6 Correct 237 ms 475504 KB Output is correct
7 Correct 572 ms 482704 KB Output is correct
8 Correct 869 ms 484488 KB Output is correct
9 Correct 605 ms 484208 KB Output is correct
10 Correct 766 ms 484376 KB Output is correct
11 Correct 654 ms 483092 KB Output is correct
12 Correct 641 ms 484552 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 474708 KB Output is correct
2 Correct 241 ms 474840 KB Output is correct
3 Correct 224 ms 474764 KB Output is correct
4 Correct 244 ms 475476 KB Output is correct
5 Correct 259 ms 475604 KB Output is correct
6 Correct 237 ms 475504 KB Output is correct
7 Correct 476 ms 482904 KB Output is correct
8 Correct 798 ms 484684 KB Output is correct
9 Correct 529 ms 483996 KB Output is correct
10 Correct 739 ms 484352 KB Output is correct
11 Correct 606 ms 483092 KB Output is correct
12 Correct 573 ms 484700 KB Output is correct
13 Correct 572 ms 482704 KB Output is correct
14 Correct 869 ms 484488 KB Output is correct
15 Correct 605 ms 484208 KB Output is correct
16 Correct 766 ms 484376 KB Output is correct
17 Correct 654 ms 483092 KB Output is correct
18 Correct 641 ms 484552 KB Output is correct
19 Correct 612 ms 485300 KB Output is correct
20 Correct 966 ms 485632 KB Output is correct
21 Correct 622 ms 484204 KB Output is correct
22 Correct 772 ms 485276 KB Output is correct
23 Correct 737 ms 483904 KB Output is correct
24 Correct 701 ms 485596 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 482012 KB Output is correct
2 Correct 794 ms 483708 KB Output is correct
3 Correct 507 ms 483940 KB Output is correct
4 Correct 694 ms 483652 KB Output is correct
5 Correct 623 ms 482916 KB Output is correct
6 Correct 561 ms 483692 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 433 ms 482012 KB Output is correct
2 Correct 794 ms 483708 KB Output is correct
3 Correct 507 ms 483940 KB Output is correct
4 Correct 694 ms 483652 KB Output is correct
5 Correct 623 ms 482916 KB Output is correct
6 Correct 561 ms 483692 KB Output is correct
7 Incorrect 734 ms 484248 KB Output isn't correct
8 Halted 0 ms 0 KB -