Submission #814192

# Submission time Handle Problem Language Result Execution time Memory
814192 2023-08-08T06:13:22 Z 반딧불(#10119) Posters on the wall (CPSPC17_posters) C++17
0 / 100
718 ms 1048576 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, lazyA, lazyB;

        Node(){
            lc = rc = nullptr;
            a = b = lazyA = lazyB = 0;
        }

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

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

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

        Node *propagate(int l, int r){
            Node *tmp = new Node();
            *tmp = *this;
            tmp->a += lazyA * (vx[r+1] - vx[l]), tmp->b += lazyB * (vx[r+1] - vx[l]);
            if(l!=r){
                tmp->lc = new Node(); *(tmp->lc) = *lc; tmp->lc->lazyA += lazyA, tmp->lc->lazyB += lazyB;
                tmp->rc = new Node(); *(tmp->rc) = *rc; tmp->rc->lazyA += lazyA, tmp->rc->lazyB += lazyB;
            }
            tmp->lazyA = tmp->lazyB = 0;
            return tmp;
        }

        Node *update(int l, int r, int s, int e, ll av, ll bv){
            Node *ret = propagate(l, r);
            if(r<s || e<l) return ret;
            if(s<=l && r<=e){
                ret->lazyA = av, ret->lazyB = bv;
                ret = ret->propagate(l, r);
                return ret;
            }
            int m = (l+r)>>1;
            ret->lc = lc->update(l, m, s, e, av, bv);
            ret->rc = rc->update(m+1, r, s, e, av, bv);
            ret->a = ret->lc->a + ret->rc->a, ret->b = ret->lc->b + ret->rc->b;
            return ret;
        }

        pair<Node*, ll> query(int l, int r, int s, int e, ll t){
            Node *ret = propagate(l, r);
            if(r<s || e<l) return make_pair(ret, 0);
            if(s<=l && r<=e) return make_pair(ret, ret->a*t+ret->b);
            int m = (l+r)>>1;
            ll rn = 0;
            pair<Node*, ll> p = ret->lc->query(l, m, s, e, t);
            ret->lc = p.first, rn += p.second;
            p = ret->rc->query(m+1, r, s, e, t);
            ret->rc = p.first, rn += p.second;
            return make_pair(ret, rn);
        }
    } *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;
        pair<Node*, ll> p = history[idx]->query(0, MX, s, e, t);
        history[idx] = p.first;
        return p.second;
    }

    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 * v) % MOD;
        x2 = (x2 + lastAns * v) % MOD;
        y1 = (y1 + lastAns * v) % MOD;
        y2 = (y2 + lastAns * 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:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |     scanf("%d %d %d %d %d", &n, &q, &n, &q, &MOD);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:125:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         scanf("%lld %lld %lld %lld %lld", &x1, &y1, &x2, &y2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 11844 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 718 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 718 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -