oj.uz

Submission #814456

# Submission time Handle Problem Language Result Execution time Memory
814456 2023-08-08T07:34:28 Z 반딧불(#10119) Posters on the wall (CPSPC17_posters) C++17
100 / 100
 624 ms 205712 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector<ll> vx;

struct segTree{
    struct Node{
        Node *lc, *rc;
        ll a, b, aSum, bSum;

        Node(){
            lc = rc = nullptr;
            a = b = aSum = bSum = 0;
        }

        Node(int l, int r){
            lc = rc = nullptr;
            a = b = aSum = bSum = 0;
            if(l==r) return;

            int m = (l+r)>>1;
            lc = new Node(l, m);
            rc = new Node(m+1, r);
        }

        Node(Node *r){
            lc = r->lc, rc = r->rc;
            a = r->a, b = r->b, aSum = r->aSum, bSum = r->bSum;
        }

        ~Node(){
            delete lc;
            delete rc;
        }

        Node *update(int l, int r, int s, int e, ll av, ll bv){
            if(r<s || e<l) return this;
            Node *tmp = new Node(this);
            if(s<=l && r<=e){
                tmp->a += av, tmp->b += bv;
                tmp->aSum += av * (vx[r+1] - vx[l]), tmp->bSum += bv * (vx[r+1] - vx[l]);
                return tmp;
            }
            int m = (l+r)>>1;
            tmp->lc = tmp->lc->update(l, m, s, e, av, bv);
            tmp->rc = tmp->rc->update(m+1, r, s, e, av, bv);
            tmp->aSum = tmp->lc->aSum + tmp->rc->aSum + tmp->a * (vx[r+1] - vx[l]);
            tmp->bSum = tmp->lc->bSum + tmp->rc->bSum + tmp->b * (vx[r+1] - vx[l]);
            return tmp;
        }

        ll query(int l, int r, int s, int e, ll t, ll aup = 0, ll bup = 0){
            if(r<s || e<l) return 0;
            if(s<=l && r<=e) return (aSum + aup * (vx[r+1] - vx[l])) * t + (bSum + bup * (vx[r+1] - vx[l]));
            int m = (l+r)>>1;
            return lc->query(l, m, s, e, t, aup+a, bup+b) + rc->query(m+1, r, s, e, t, aup+a, bup+b);
        }
    } *root;

    Node *history[400002]; int historyCnt;
    ll times[400002];

    int MX;
    void init(int maxX){
        MX = maxX, historyCnt = 0;
        history[historyCnt] = root = new Node(0, MX);
        times[historyCnt] = -1e9;
        historyCnt++;
    }

    void update(int s, int e, ll av, ll bv){
        root = root->update(0, MX, s, e, av, bv);
    }

    void step(ll t){
        history[historyCnt] = root;
        times[historyCnt] = t;
        historyCnt++;
    }

    ll query(int s, int e, ll t){
        int idx = upper_bound(times, times+historyCnt, t) - times - 1;
        return history[idx]->query(0, MX, s, e, t);
    }

    ll query(int s, int e, ll t1, ll t2){
        return query(s, e, t2) - query(s, e, t1-1);
    }
} tree;

struct Event{
    int type; ll y, l, r, a, b; /// type: 0 ���簢�� ����, 1 ���簢�� �߰�, 2 ����
    Event(){}
    Event(int type, ll y, ll l, ll r, ll a, ll b): type(type), y(y), l(l), r(r), a(a), b(b){}
    bool operator<(const Event &r)const{
        if(y!=r.y) return y<r.y;
        return type<r.type;
    }
};

int n, q, MOD;
vector<Event> vec;
ll ans[50002];

int main(){
    scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
    for(int i=1; i<=n; i++){
        ll x1, y1, x2, y2;
        scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
        if(x1>x2) swap(x1, x2);
        if(y1>y2) swap(y1, y2);
        x1++, y1++;
        /// [x1, x2] [y1, y2] ������ ���ϴ� ������ �Է��� �ٲ�
        vec.push_back(Event(1, y1, x1, x2, 1, -y1+1));
        vec.push_back(Event(0, y2+1, x1, x2, -1, y2));
    }

    for(Event &p: vec){
        vx.push_back(p.l);
        vx.push_back(p.r+1);
    }
    sort(vx.begin(), vx.end());
    vx.erase(unique(vx.begin(), vx.end()), vx.end());
    for(Event &p: vec){
        p.l = lower_bound(vx.begin(), vx.end(), p.l) - vx.begin();
        p.r = lower_bound(vx.begin(), vx.end(), p.r+1) - vx.begin() - 1;
    }

    sort(vec.begin(), vec.end());
    const int MX = (int)vx.size() - 2;
    tree.init(MX);
    for(Event &p: vec){
        tree.update(p.l, p.r, p.a, p.b);
        tree.step(p.y);
    }

    ll lastAns = 0;
    for(int i=1; i<=q; i++){
        ll x1, y1, x2, y2, v;
        scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
        x1 = (x1 + lastAns % MOD * v) % MOD;
        x2 = (x2 + lastAns % MOD * v) % MOD;
        y1 = (y1 + lastAns % MOD * v) % MOD;
        y2 = (y2 + lastAns % MOD * v) % MOD;
        if(x1>x2) swap(x1, x2);
        if(y1>y2) swap(y1, y2);
        x1++, y1++;

        x1 = max(x1, vx[0]), x2 = min(x2, vx.back()-1);
        if(x1 <= x2 && y1 <= y2){
            int idx1 = lower_bound(vx.begin(), vx.end(), x1) - vx.begin();
            int idx2 = upper_bound(vx.begin(), vx.end(), x2) - vx.begin() - 1;
            lastAns = 0;

            if(idx1 > idx2){ /// ���� ��ü�� �ϳ��� ������ ��� ����
                int i = idx2;
                lastAns = tree.query(i, i, y1, y2) / (vx[i+1] - vx[i]) * (x2-x1+1);
            }
            else{
                if(idx1 < idx2) lastAns = tree.query(idx1, idx2-1, y1, y2);
                if(idx1 && x1 < vx[idx1])
                    lastAns += tree.query(idx1-1, idx1-1, y1, y2) / (vx[idx1] - vx[idx1-1]) * (vx[idx1] - x1);
                if(idx2 <= MX && vx[idx2] <= x2)
                    lastAns += tree.query(idx2, idx2, y1, y2) / (vx[idx2+1] - vx[idx2]) * (x2 - vx[idx2] + 1);
            }
        }
        else lastAns = 0;
        printf("%lld\n", lastAns);
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:109:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |     scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:112:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:143:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |         scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 23 ms 12136 KB Output is correct
5 Correct 25 ms 13496 KB Output is correct
6 Correct 21 ms 9384 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 23 ms 12136 KB Output is correct
5 Correct 25 ms 13496 KB Output is correct
6 Correct 21 ms 9384 KB Output is correct
7 Correct 218 ms 124336 KB Output is correct
8 Correct 581 ms 191424 KB Output is correct
9 Correct 353 ms 201868 KB Output is correct
10 Correct 500 ms 179876 KB Output is correct
11 Correct 447 ms 197496 KB Output is correct
12 Correct 350 ms 122164 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 23 ms 12136 KB Output is correct
5 Correct 25 ms 13496 KB Output is correct
6 Correct 21 ms 9384 KB Output is correct
7 Correct 290 ms 204780 KB Output is correct
8 Correct 595 ms 198632 KB Output is correct
9 Correct 369 ms 201964 KB Output is correct
10 Correct 535 ms 185696 KB Output is correct
11 Correct 464 ms 203568 KB Output is correct
12 Correct 365 ms 124256 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 980 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 2 ms 980 KB Output is correct
4 Correct 23 ms 12136 KB Output is correct
5 Correct 25 ms 13496 KB Output is correct
6 Correct 21 ms 9384 KB Output is correct
7 Correct 218 ms 124336 KB Output is correct
8 Correct 581 ms 191424 KB Output is correct
9 Correct 353 ms 201868 KB Output is correct
10 Correct 500 ms 179876 KB Output is correct
11 Correct 447 ms 197496 KB Output is correct
12 Correct 350 ms 122164 KB Output is correct
13 Correct 290 ms 204780 KB Output is correct
14 Correct 595 ms 198632 KB Output is correct
15 Correct 369 ms 201964 KB Output is correct
16 Correct 535 ms 185696 KB Output is correct
17 Correct 464 ms 203568 KB Output is correct
18 Correct 365 ms 124256 KB Output is correct
19 Correct 298 ms 205064 KB Output is correct
20 Correct 616 ms 199120 KB Output is correct
21 Correct 354 ms 202124 KB Output is correct
22 Correct 542 ms 185740 KB Output is correct
23 Correct 438 ms 203992 KB Output is correct
24 Correct 374 ms 124592 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 109248 KB Output is correct
2 Correct 554 ms 179172 KB Output is correct
3 Correct 347 ms 201788 KB Output is correct
4 Correct 489 ms 170300 KB Output is correct
5 Correct 411 ms 185380 KB Output is correct
6 Correct 344 ms 120256 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 109248 KB Output is correct
2 Correct 554 ms 179172 KB Output is correct
3 Correct 347 ms 201788 KB Output is correct
4 Correct 489 ms 170300 KB Output is correct
5 Correct 411 ms 185380 KB Output is correct
6 Correct 344 ms 120256 KB Output is correct
7 Correct 310 ms 205056 KB Output is correct
8 Correct 624 ms 200656 KB Output is correct
9 Correct 379 ms 203464 KB Output is correct
10 Correct 554 ms 187204 KB Output is correct
11 Correct 453 ms 205712 KB Output is correct
12 Correct 369 ms 126344 KB Output is correct