oj.uz

Submission #427246

# Submission time Handle Problem Language Result Execution time Memory
427246 2021-06-14T13:46:31 Z model_code Posters on the wall (CPSPC17_posters) C++17
100 / 100
 1930 ms 285476 KB 
#include<bits/stdc++.h>
#include<unistd.h>

using namespace std;

#define mp(x,y) make_pair(x, y)
#define For(i, n) for (int i = 0; i < (int) n; i++)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;

struct node {
    ll length;
    ll begin, end;
    ll open, sum;
    ll openlazy, sumlazy;
    node *left, *right;

    node(node* orig); 

    node(ll bbeg, ll eend, node* lleft, node* rright);
};

map<ll, ll> compress;
node* def_node;
vector<node*> nodes;
vector<ll> decompress;

node::node(ll bbeg, ll eend, node* lleft, node* rright) :
    length(eend - bbeg), begin(bbeg), end(eend), open(0), sum(0), openlazy(0), sumlazy(0), left(lleft), right(rright) {nodes.push_back(this);}

node::node(node* orig) : 
    length(orig->length), begin(orig->begin),
    end(orig->end), open(orig->open),
    sum(orig->sum), openlazy(orig->openlazy),
    sumlazy(orig->sumlazy), left(orig->left), 
    right(orig->right) {nodes.push_back(this);}

node* construct(ll first, ll last) {
    if (first == last) return def_node;
    node *left = nullptr, *right = nullptr;
    if (last - first > 1) {
        left = construct(first, (first + last) / 2);
        right = construct((first + last) / 2, last);
    }
    return new node(decompress [first], decompress [last], left, right);
}

node* update(node* curnode, ll x, ll y1, ll y2, ll mod) {
    if (y1 <= curnode->begin && y2 >= curnode->end) {
        node* newnode = new node(curnode);
        newnode->sum -= x * mod * newnode->length;
        newnode->open += mod * newnode->length;
        newnode->openlazy += mod;
        newnode->sumlazy -= mod * x;

        return newnode;
    }
    else if (y1 < curnode->end && y2 > curnode->begin) {
        node  *left = update(curnode->left, x, y1, y2, mod),
              *right = update(curnode->right, x, y1, y2, mod);

        node* newnode = new node(curnode);
        newnode->sum = left->sum + right->sum + curnode->sumlazy * newnode->length;
        newnode->open = left->open + right->open + curnode->openlazy * newnode->length;
        newnode->left = left;
        newnode->right = right;

        return newnode;
    }
    return curnode;
}

pii fetch(node* curnode, ll y1, ll y2, ll sumlazy, ll openlazy) {
//    cerr << "Fetch " << y1 << ' ' << y2 << ' ' << curnode->begin << ' ' << curnode->end << ' ' << sumlazy << ' ' << openlazy << endl;
    if (y1 <= curnode->begin && y2 >= curnode->end) {
        return mp(curnode->sum + sumlazy * curnode->length,curnode->open + openlazy * curnode->length);
    }

    else if (y1 < curnode->end && y2 > curnode->begin) {
        if (curnode->left == nullptr) {
            ll realsum = curnode->sum + curnode->length * sumlazy;
            ll realopen = curnode->open + curnode->length * openlazy;
            ll intersect = min(y2, curnode->end) - max(y1, curnode->begin);
//            cerr << "Magic result " << curnode->length << ' ' << intersect << ' ' << realsum << ' ' << realopen << endl;
            return mp(realsum / curnode->length * intersect, realopen / curnode->length * intersect);
        }
        else {
            pii leftv = fetch(curnode->left, y1, y2, sumlazy + curnode->sumlazy, openlazy + curnode->openlazy);
            pii rightv = fetch(curnode->right, y1, y2, sumlazy + curnode->sumlazy, openlazy + curnode->openlazy);
            return mp(leftv.first + rightv.first, leftv.second + rightv.second);
        }
    }

    return mp(0, 0);
}

int main () {

    def_node = new node(-1000, -1000, nullptr, nullptr);
    srand(time(NULL) + getpid());

    ll r, c, n, q, MOD;
    cin >> r >> c >> n >> q >> MOD;
    decompress = {0, 1023456789};
    vector<pair<pii, pii> > events;
    For(i, n) {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);

        if (y1 < 0 || x1 < 0 || x1 > r || y2 > c || x1 == x2 || y1 == y2) {
            cerr << "BAD INPUT A! " << i << "\n";
            return 1;
        }
        decompress.push_back(y1);
        decompress.push_back(y2);
        events.push_back(mp(mp(x1, 1), mp(y1, y2)));
        events.push_back(mp(mp(x2, -1), mp(y1, y2)));
    }
    sort(decompress.begin(), decompress.end());
    decompress.resize(int(unique(decompress.begin(), decompress.end()) - decompress.begin()));

    For(i, decompress.size()) {
        compress [decompress [i]] = i;
    }

    map<ll, node*> roots;
    roots [0] = construct(0, decompress.size() - 1);
 

    sort(events.begin(), events.end());
    for(auto& event : events) {
        ll last = (--(roots.end()))->first;
        roots[event.first.first] = update( roots[last], event.first.first, event.second.first, event.second.second, event.first.second);
    }

    ll lastres = 0;

    For(i, q) {
        ll x1, y1, x2, y2, mod;
        cin >> x1 >> y1 >> x2 >> y2 >> mod;
        mod = ((mod % MOD) * (lastres % MOD)) % MOD;

        x1 = (x1 + mod) % MOD; y1 = (y1 + mod) % MOD; x2 = (x2 + mod) % MOD; y2 = (y2 + mod) % MOD;
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);

        if (y1 < 0 || x1 < 0 || x1 > r || y2 > c || x1 == x2 || y1 == y2) {
            cerr << "BAD INPUT B! " << i << "\n";
            return 1;
        }

//        cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
        ll startx = (--(roots.upper_bound(x1)))->first;
        ll endx = (--(roots.upper_bound(x2)))->first;
        pii left = fetch(roots[startx], y1, y2, 0, 0);
        pii right = fetch(roots[endx], y1, y2, 0, 0);

//        cerr << left.first << ' ' << left.second << ' ' << right.first << ' ' << right.second << endl;

        ll leftres = x1 * left.second + left.first;
        ll rightres = x2 * right.second + right.first;
//        cerr << leftres << ' ' << rightres << endl;
        lastres = rightres - leftres;
        printf("%lld\n", lastres);
    }

    for(auto ptr : nodes) delete ptr;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 69 ms 16328 KB Output is correct
5 Correct 59 ms 13864 KB Output is correct
6 Correct 63 ms 16568 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 69 ms 16328 KB Output is correct
5 Correct 59 ms 13864 KB Output is correct
6 Correct 63 ms 16568 KB Output is correct
7 Correct 665 ms 171692 KB Output is correct
8 Correct 1652 ms 264900 KB Output is correct
9 Correct 1174 ms 276620 KB Output is correct
10 Correct 1425 ms 248840 KB Output is correct
11 Correct 1125 ms 169200 KB Output is correct
12 Correct 1255 ms 272068 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 69 ms 16328 KB Output is correct
5 Correct 59 ms 13864 KB Output is correct
6 Correct 63 ms 16568 KB Output is correct
7 Correct 657 ms 165500 KB Output is correct
8 Correct 1628 ms 261492 KB Output is correct
9 Correct 1068 ms 276772 KB Output is correct
10 Correct 1339 ms 246116 KB Output is correct
11 Correct 1002 ms 169052 KB Output is correct
12 Correct 1317 ms 268388 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 4 ms 1356 KB Output is correct
3 Correct 5 ms 1356 KB Output is correct
4 Correct 69 ms 16328 KB Output is correct
5 Correct 59 ms 13864 KB Output is correct
6 Correct 63 ms 16568 KB Output is correct
7 Correct 665 ms 171692 KB Output is correct
8 Correct 1652 ms 264900 KB Output is correct
9 Correct 1174 ms 276620 KB Output is correct
10 Correct 1425 ms 248840 KB Output is correct
11 Correct 1125 ms 169200 KB Output is correct
12 Correct 1255 ms 272068 KB Output is correct
13 Correct 657 ms 165500 KB Output is correct
14 Correct 1628 ms 261492 KB Output is correct
15 Correct 1068 ms 276772 KB Output is correct
16 Correct 1339 ms 246116 KB Output is correct
17 Correct 1002 ms 169052 KB Output is correct
18 Correct 1317 ms 268388 KB Output is correct
19 Correct 946 ms 285476 KB Output is correct
20 Correct 1596 ms 275832 KB Output is correct
21 Correct 1225 ms 277020 KB Output is correct
22 Correct 1675 ms 258680 KB Output is correct
23 Correct 1222 ms 173612 KB Output is correct
24 Correct 1485 ms 282384 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 150600 KB Output is correct
2 Correct 1602 ms 245992 KB Output is correct
3 Correct 1104 ms 276624 KB Output is correct
4 Correct 1279 ms 234020 KB Output is correct
5 Correct 1060 ms 164632 KB Output is correct
6 Correct 1246 ms 253796 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 150600 KB Output is correct
2 Correct 1602 ms 245992 KB Output is correct
3 Correct 1104 ms 276624 KB Output is correct
4 Correct 1279 ms 234020 KB Output is correct
5 Correct 1060 ms 164632 KB Output is correct
6 Correct 1246 ms 253796 KB Output is correct
7 Correct 1237 ms 285272 KB Output is correct
8 Correct 1930 ms 275800 KB Output is correct
9 Correct 1284 ms 276848 KB Output is correct
10 Correct 1667 ms 258916 KB Output is correct
11 Correct 1257 ms 173392 KB Output is correct
12 Correct 1448 ms 282268 KB Output is correct