oj.uz

Submission #428128

# Submission time Handle Problem Language Result Execution time Memory
428128 2021-06-15T08:16:11 Z 반딧불(#7617) Posters on the wall (CPSPC17_posters) C++17
20 / 100
 3428 ms 1048580 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;

//vector<ll> xVec, yVec;

struct xNode {
    struct yNode {
        ll globalSum, globalLazy;
        ll totalSum, totalLazy;
        yNode *lchild, *rchild;

        yNode(){
            globalSum = globalLazy = totalSum = totalLazy = 0;
            lchild = rchild = nullptr;
        }

        ~yNode(){
            if(lchild) delete lchild;
            if(rchild) delete rchild;
        }

        inline void update(int l, int r, int s, int e, ll bonus, ll len, bool same){
            if(l==s && r==e){
                if(same){
                    globalSum += 1 * (e-s);
                    globalLazy += 1;
                }
                totalSum += len * (e-s);
                totalLazy += len;
                return;
            }
            int m = (l+r)/2;
            if(s<m){
                if(!lchild) lchild = new yNode();
                lchild->update(l, m, s, min(m, e), bonus, len, same);
            }
            if(m<e){
                if(!rchild) rchild = new yNode();
                rchild->update(m, r, max(s, m), e, bonus, len, same);
            }
            if(same){
                globalSum = (lchild ? lchild->globalSum : 0) + (rchild ? rchild->globalSum : 0) + globalLazy * (r-l);
            }
            totalSum = (lchild ? lchild->totalSum : 0) + (rchild ? rchild->totalSum : 0) + totalLazy * (r-l);
        }
    };
    yNode *tree;
    xNode *lchild, *rchild;

    xNode(){
        tree = nullptr;
        lchild = rchild = nullptr;
    }

    ~xNode(){
        if(tree) delete tree;
        if(lchild) delete lchild;
        if(rchild) delete rchild;
    }

    inline void update(int xl, int xr, int yl, int yr, int xs, int xe, int ys, int ye){
//        ll len = xVec[xe] - xVec[xs];
        ll len = xe-xs;
        if(xl != xs || xr != xe){
            int m = (xl+xr)/2;
            if(xs < m){
                if(!lchild) lchild = new xNode();
                lchild->update(xl, m, yl, yr, xs, min(m, xe), ys, ye);
            }
            if(m < xe){
                if(!rchild) rchild = new xNode();
                rchild->update(m, xr, yl, yr, max(xs, m), xe, ys, ye);
            }
        }
        if(!tree) tree = new yNode();
        tree->update(yl, yr, ys, ye, xr-xl, len, xl==xs && xr==xe);
    }
} *tree;

inline ll query(xNode::yNode *i, int l, int r, int s, int e, ll lazySum, ll len, bool same){
    ll ret = 0;
    if(l==s && r==e){
        if(same){
            if(i) ret += i->totalSum;
            ret += lazySum * (r-l);
        }
        else{
            if(i) ret += i->globalSum * len;
            ret += lazySum * len * (r-l);
        }
        return ret;
    }
    lazySum = !i ? lazySum : (lazySum + (same ? i->totalLazy : i->globalLazy));
    int m = (l+r)/2;
    if(s<m) ret += query(i ? i->lchild : nullptr, l, m, s, min(m, e), lazySum, len, same);
    if(m<e) ret += query(i ? i->rchild : nullptr, m, r, max(s, m), e, lazySum, len, same);
    return ret;
}

int _yl, _yr, _ys, _ye;
inline ll query(xNode *i, int xl, int xr, int xs, int xe){
    ll len = xe-xs;
    ll ret = query(i->tree, _yl, _yr, _ys, _ye, 0, len, xl==xs && xr==xe);
    if(xl!=xs || xr!=xe){
        int m = (xl+xr)/2;
        if(xs<m && i->lchild) ret += query(i->lchild, xl, m, xs, min(m, xe));
        if(m<xe && i->rchild) ret += query(i->rchild, m, xr, max(xs, m), xe);
    }
    return ret;
}

int r, c, n, q, m, N, M;
ll _x1[50002], _y1[50002], _x2[50002], _y2[50002];

ll query(int xs, int xe, int ys, int ye){
    _yl = 0, _yr = M-1, _ys = ys, _ye = ye;
    return query(tree, 0, N-1, xs, xe);
}

int main(){
    scanf("%d %d %d %d %d", &r, &c, &n, &q, &m);
    N = r+1, M = c+1;
//    xVec.push_back(0), xVec.push_back(r);
//    yVec.push_back(0), yVec.push_back(c);
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld %lld", &_x1[i], &_y1[i], &_x2[i], &_y2[i]);
        if(_x1[i] > _x2[i]) swap(_x1[i], _x2[i]);
        if(_y1[i] > _y2[i]) swap(_y1[i], _y2[i]);
//        xVec.push_back(_x1[i]), xVec.push_back(_x2[i]);
//        yVec.push_back(_y1[i]), yVec.push_back(_y2[i]);
    }
//    sort(xVec.begin(), xVec.end());
//    xVec.erase(unique(xVec.begin(), xVec.end()), xVec.end());
//    sort(yVec.begin(), yVec.end());
//    yVec.erase(unique(yVec.begin(), yVec.end()), yVec.end());
//    N = (int)xVec.size(), M = (int)yVec.size();

    tree = new xNode();
    for(int i=1; i<=n; i++){
//        _x1[i] = lower_bound(xVec.begin(), xVec.end(), _x1[i]) - xVec.begin();
//        _x2[i] = lower_bound(xVec.begin(), xVec.end(), _x2[i]) - xVec.begin();
//        _y1[i] = lower_bound(yVec.begin(), yVec.end(), _y1[i]) - yVec.begin();
//        _y2[i] = lower_bound(yVec.begin(), yVec.end(), _y2[i]) - yVec.begin();
        tree->update(0, N-1, 0, M-1, _x1[i], _x2[i], _y1[i], _y2[i]);
    }

    ll ans = 0;
    for(int i=1; i<=q; i++){
        ll qx1, qy1, qx2, qy2, v;
        scanf("%lld %lld %lld %lld %lld", &qx1, &qy1, &qx2, &qy2, &v);
        ans %= m, v %= m;
        qx1 = (qx1 + ans * v) % m;
        qx2 = (qx2 + ans * v) % m;
        qy1 = (qy1 + ans * v) % m;
        qy2 = (qy2 + ans * v) % m;
        if(qx1 > qx2) swap(qx1, qx2);
        if(qy1 > qy2) swap(qy1, qy2);

        ans = query(qx1, qx2, qy1, qy2);
        printf("%lld\n", ans);
        continue;

//        int xl = upper_bound(xVec.begin(), xVec.end(), qx1) - xVec.begin() - 1;
//        int xr = lower_bound(xVec.begin(), xVec.end(), qx2) - xVec.begin();
//        int yl = upper_bound(yVec.begin(), yVec.end(), qy1) - yVec.begin() - 1;
//        int yr = lower_bound(yVec.begin(), yVec.end(), qy2) - yVec.begin();
//
//        bool xSingle = (xr-xl == 1);
//        bool ySingle = (yr-yl == 1);
//
//        ans = 0;
//        if(xSingle && ySingle){
//            ans = !!query(xl, xr, yl, yr) * (qx2 - qx1) * (qy2 - qy1);
//        }
//        else if(xSingle){
//            ans = query(xl, xr, yl+1, yr-1) / (xVec[xr] - xVec[xl]) * (qx2 - qx1);
//            ans += !!query(xl, xr, yl, yl+1) * (qx2 - qx1) * (yVec[yl+1] - qy1);
//            ans += !!query(xl, xr, yr-1, yr) * (qx2 - qx1) * (qy2 - yVec[yr-1]);
//        }
//        else if(ySingle){
//            ans = query(xl+1, xr-1, yl, yr) / (yVec[yr] - yVec[yl]) * (qy2 - qy1);
//            ans += !!query(xl, xl+1, yl, yr) * (qy2 - qy1) * (xVec[xl+1] - qx1);
//            ans += !!query(xr-1, xr, yl, yr) * (qy2 - qy1) * (qx2 - xVec[xr-1]);
//        }
//        else{
//            ans += query(xl+1, xr-1, yl+1, yr-1); /// Center
//
//            ans += query(xl+1, xr-1, yl, yl+1) / (yVec[yl+1] - yVec[yl]) * (yVec[yl+1] - qy1); /// Left
//            ans += query(xl+1, xr-1, yr-1, yr) / (yVec[yr] - yVec[yr-1]) * (qy2 - yVec[yr-1]); /// Right
//            ans += query(xl, xl+1, yl+1, yr-1) / (xVec[xl+1] - xVec[xl]) * (xVec[xl+1] - qx1); /// Down
//            ans += query(xr-1, xr, yl+1, yr-1) / (xVec[xr] - xVec[xr-1]) * (qx2 - xVec[xr-1]); /// Up
//
//            ans += !!query(xl, xl+1, yl, yl+1) * (xVec[xl+1] - qx1) * (yVec[yl+1] - qy1);
//            ans += !!query(xl, xl+1, yr-1, yr) * (xVec[xl+1] - qx1) * (qy2 - yVec[yr-1]);
//            ans += !!query(xr-1, xr, yl, yl+1) * (qx2 - xVec[xr-1]) * (yVec[yl+1] - qy1);
//            ans += !!query(xr-1, xr, yr-1, yr) * (qx2 - xVec[xr-1]) * (qy2 - yVec[yr-1]);
//        }
//
//        printf("%lld\n", ans);
    }

    delete tree;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:127:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |     scanf("%d %d %d %d %d", &r, &c, &n, &q, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf("%lld %lld %lld %lld", &_x1[i], &_y1[i], &_x2[i], &_y2[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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", &qx1, &qy1, &qx2, &qy2, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2744 KB Output is correct
2 Correct 8 ms 2764 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2744 KB Output is correct
2 Correct 8 ms 2764 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 236 ms 58604 KB Output is correct
5 Correct 199 ms 40760 KB Output is correct
6 Correct 179 ms 38796 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2744 KB Output is correct
2 Correct 8 ms 2764 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 236 ms 58604 KB Output is correct
5 Correct 199 ms 40760 KB Output is correct
6 Correct 179 ms 38796 KB Output is correct
7 Correct 3428 ms 868628 KB Output is correct
8 Runtime error 1493 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2744 KB Output is correct
2 Correct 8 ms 2764 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 236 ms 58604 KB Output is correct
5 Correct 199 ms 40760 KB Output is correct
6 Correct 179 ms 38796 KB Output is correct
7 Runtime error 1615 ms 1048580 KB Execution killed with signal 9
8 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2744 KB Output is correct
2 Correct 8 ms 2764 KB Output is correct
3 Correct 7 ms 2636 KB Output is correct
4 Correct 236 ms 58604 KB Output is correct
5 Correct 199 ms 40760 KB Output is correct
6 Correct 179 ms 38796 KB Output is correct
7 Correct 3428 ms 868628 KB Output is correct
8 Runtime error 1493 ms 1048580 KB Execution killed with signal 9
9 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 323444 KB Output is correct
2 Runtime error 1828 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 323444 KB Output is correct
2 Runtime error 1828 ms 1048580 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -