oj.uz

Submission #428655

# Submission time Handle Problem Language Result Execution time Memory
428655 2021-06-15T13:33:43 Z 최서현(#7487) Posters on the wall (CPSPC17_posters) C++17
80 / 100
 1071 ms 1048580 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#define pii pair<int, int>
#define tiii pair<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;
    vector<pii> ls[c];
    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);
        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, y * t, x * t, 1ll * x * y * t);
    }

    long long pr = 0;
    while(T--)
    {
        int x1, x2, y1, y2, v; cin >> x1 >> y1 >> x2 >> y2 >> v;
        x1 = (x1 + pr * v) % m;
        x2 = (x2 + pr * v) % m;
        y1 = (y1 + pr * v) % m;
        y2 = (y2 + pr * v) % m;
        if(x1 > x2) swap(x1, x2);
        if(y1 > y2) swap(y1, y2);
//        cout << qry(root[y2], 0, r, 0, x2, x2, y2) << endl;
        pr = qry(root[y2], 0, r, 0, x2, x2, y2) - qry(root[y2], 0, r, 0, x1, x1, y2)
                -qry(root[y1], 0, r, 0, x2, x2, y1) + qry(root[y1], 0, r, 0, x1, x1, y1);
        cout << pr << '\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:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = s + e >> 1;
      |               ~~^~~
Main.cpp: In function 'long long int qry(int, int, int, int, int, int, int)':
Main.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |     int mid = s + e >> 1;
      |               ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 790920 KB Output is correct
2 Correct 366 ms 790972 KB Output is correct
3 Correct 375 ms 790920 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 790920 KB Output is correct
2 Correct 366 ms 790972 KB Output is correct
3 Correct 375 ms 790920 KB Output is correct
4 Correct 438 ms 791372 KB Output is correct
5 Correct 378 ms 791384 KB Output is correct
6 Correct 397 ms 791396 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 790920 KB Output is correct
2 Correct 366 ms 790972 KB Output is correct
3 Correct 375 ms 790920 KB Output is correct
4 Correct 438 ms 791372 KB Output is correct
5 Correct 378 ms 791384 KB Output is correct
6 Correct 397 ms 791396 KB Output is correct
7 Correct 601 ms 802092 KB Output is correct
8 Correct 900 ms 802608 KB Output is correct
9 Correct 656 ms 802512 KB Output is correct
10 Correct 806 ms 802592 KB Output is correct
11 Correct 724 ms 802240 KB Output is correct
12 Correct 667 ms 802532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 790920 KB Output is correct
2 Correct 366 ms 790972 KB Output is correct
3 Correct 375 ms 790920 KB Output is correct
4 Correct 438 ms 791372 KB Output is correct
5 Correct 378 ms 791384 KB Output is correct
6 Correct 397 ms 791396 KB Output is correct
7 Correct 708 ms 799332 KB Output is correct
8 Correct 1071 ms 799824 KB Output is correct
9 Correct 703 ms 799944 KB Output is correct
10 Correct 935 ms 799932 KB Output is correct
11 Correct 953 ms 799500 KB Output is correct
12 Correct 829 ms 799804 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 790920 KB Output is correct
2 Correct 366 ms 790972 KB Output is correct
3 Correct 375 ms 790920 KB Output is correct
4 Correct 438 ms 791372 KB Output is correct
5 Correct 378 ms 791384 KB Output is correct
6 Correct 397 ms 791396 KB Output is correct
7 Correct 601 ms 802092 KB Output is correct
8 Correct 900 ms 802608 KB Output is correct
9 Correct 656 ms 802512 KB Output is correct
10 Correct 806 ms 802592 KB Output is correct
11 Correct 724 ms 802240 KB Output is correct
12 Correct 667 ms 802532 KB Output is correct
13 Correct 708 ms 799332 KB Output is correct
14 Correct 1071 ms 799824 KB Output is correct
15 Correct 703 ms 799944 KB Output is correct
16 Correct 935 ms 799932 KB Output is correct
17 Correct 953 ms 799500 KB Output is correct
18 Correct 829 ms 799804 KB Output is correct
19 Runtime error 491 ms 1048580 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 796204 KB Output is correct
2 Correct 894 ms 796784 KB Output is correct
3 Correct 628 ms 796932 KB Output is correct
4 Correct 808 ms 796704 KB Output is correct
5 Correct 740 ms 796652 KB Output is correct
6 Correct 699 ms 796720 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 676 ms 796204 KB Output is correct
2 Correct 894 ms 796784 KB Output is correct
3 Correct 628 ms 796932 KB Output is correct
4 Correct 808 ms 796704 KB Output is correct
5 Correct 740 ms 796652 KB Output is correct
6 Correct 699 ms 796720 KB Output is correct
7 Runtime error 486 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -