IyfYuC - Online C++0x Compiler & Debugging Tool

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

#define file "o"
#define ff(i, a, b) for (auto i=(a); i<=(b); ++i)
#define ffr(i, b, a) for (auto i=(b); i>=(a); --i)
#define nl "\n"
#define ss " "
#define pb emplace_back
#define fi first
#define se second
#define sz(s) (int)s.size()
#define all(s) (s).begin(), (s).end()
#define ms(a,x) memset(a, x, sizeof (a))
#define cn continue
#define re exit(0)

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll ran(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rng); }

inline void rf() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen(file".inp","r")) {
        freopen(file".inp","r",stdin);
        freopen(file".out","w",stdout);
    }
}

const int mod = 1e9+7;

struct Upd {
    int xa, ya, xb, yb, t;
    ll w;
};

int main() {
    rf();

    int K, P;
    if(!(cin >> K >> P)) return 0;

    vector<Upd> ups(P);
    int maxT = 0;

    // Tổng năng lượng S bằng hiệu 2D toàn cục
    vector<vector<ll>> D(K+3, vector<ll>(K+3, 0));

    ff(i,0,P-1){
        int xa, ya, xb, yb, t; ll w;
        cin >> xa >> ya >> xb >> yb >> t >> w;
        if(xa>xb) swap(xa,xb);
        if(ya>yb) swap(ya,yb);
        ups[i] = {xa,ya,xb,yb,t,w};
        maxT = max(maxT, t);

        // Cập nhật tổng S (không phân biệt kênh)
        D[xa][ya]     += w;
        D[xb+1][ya]   -= w;
        D[xa][yb+1]   -= w;
        D[xb+1][yb+1] += w;
    }

    // Prefix 2D -> S
    vector<vector<ll>> S(K+2, vector<ll>(K+2,0));
    ff(x,1,K){
        ll run=0;
        ff(y,1,K){
            run += D[x][y];
            S[x][y] = S[x-1][y] + run;
        }
    }

    // Gom chỉ số update theo kênh để xác minh nhanh
    vector<vector<int>> byT(maxT+1);
    ff(i,0,P-1) byT[ups[i].t].push_back(i);

    // Chia khối
    const int B = 32; // 32~40 là ổn
    int BX = (K + B - 1) / B, BY = (K + B - 1) / B;

    struct BlockInfo {
        int cand = 0;   // ứng viên Boyer–Moore
        ll bal = 0;     // cân bằng
        vector<int> border; // danh sách update cắt biên khối
    };
    vector<vector<BlockInfo>> blk(BX, vector<BlockInfo>(BY));

    auto blockBounds = [&](int bx, int by) {
        int xl = bx*B + 1, xr = min(K, (bx+1)*B);
        int yl = by*B + 1, yr = min(K, (by+1)*B);
        return array<int,4>{xl,yl,xr,yr};
    };

    auto fullyCover = [&](const Upd& u, int bx, int by)->bool{
        auto b = blockBounds(bx,by);
        return (u.xa <= b[0] && b[2] <= u.xb && u.ya <= b[1] && b[3] <= u.yb);
    };

    auto overlap = [&](const Upd& u, int bx, int by)->bool{
        auto b = blockBounds(bx,by);
        if (u.xa > b[2] || u.xb < b[0] || u.ya > b[3] || u.yb < b[1]) return false;
        return true;
    };

    // Boyer–Moore theo khối + gom border
    for(int i=0;i<P;++i){
        const auto &u = ups[i];
        int bx1 = (u.xa-1)/B, bx2 = (u.xb-1)/B;
        int by1 = (u.ya-1)/B, by2 = (u.yb-1)/B;

        for(int bx=bx1; bx<=bx2; ++bx){
            for(int by=by1; by<=by2; ++by){
                if(fullyCover(u,bx,by)){
                    auto &bi = blk[bx][by];
                    if(bi.cand==u.t){ bi.bal += u.w; }
                    else{
                        if(bi.bal >= u.w) bi.bal -= u.w;
                        else { bi.cand = u.t; bi.bal = u.w - bi.bal; }
                    }
                }else if(overlap(u,bx,by)){
                    blk[bx][by].border.push_back(i);
                }
            }
        }
    }

    // Kết quả
    vector<vector<int>> ans(K+1, vector<int>(K+1, 0));

    // Xác minh cho từng khối
    for(int bx=0; bx<BX; ++bx){
        for(int by=0; by<BY; ++by){
            auto b = blockBounds(bx,by);
            int xl=b[0], yl=b[1], xr=b[2], yr=b[3];
            int nx = xr-xl+1, ny = yr-yl+1;

            // Tập kênh cần kiểm tra
            vector<int> candList;
            {
                unordered_set<int> seen;
                if(blk[bx][by].cand) { seen.insert(blk[bx][by].cand); candList.push_back(blk[bx][by].cand); }
                for(int id: blk[bx][by].border){
                    int t = ups[id].t;
                    if(!seen.count(t)){ seen.insert(t); candList.push_back(t); }
                }
            }

            // Nếu không có ứng viên nào (rất hiếm) → chắc chắn 0
            if(candList.empty()){
                ff(x,xl,xr) ff(y,yl,yr) ans[x][y]=0;
                continue;
            }

            // Với mỗi kênh ứng viên, tính năng lượng trong khối bằng hiệu 2D cục bộ và kiểm tra
            // Nếu tìm được kênh thắng, gán ngay (không thể có 2 kênh > 1/2).
            // Đầu tiên, mặc định là 0
            ff(x,xl,xr) ff(y,yl,yr) ans[x][y]=0;

            for(int t : candList){
                // diff cục bộ
                vector<vector<ll>> Dloc(nx+2, vector<ll>(ny+2, 0));
                ll baseAll = 0;

                // duyệt tất cả update của kênh t
                for(int id : byT[t]){
                    const auto &u = ups[id];
                    if(u.xa>xr || u.xb<xl || u.ya>yr || u.yb<yl) continue; // không giao

                    if(u.xa<=xl && xr<=u.xb && u.ya<=yl && yr<=u.yb){
                        // phủ trọn khối
                        baseAll += u.w;
                    }else{
                        // giao cục bộ
                        int xa=max(u.xa,xl), xb=min(u.xb,xr);
                        int ya=max(u.ya,yl), yb=min(u.yb,yr);
                        // chuyển sang chỉ số 1..nx,1..ny
                        int x1=xa-xl+1, x2=xb-xl+1;
                        int y1=ya-yl+1, y2=yb-yl+1;
                        Dloc[x1][y1]       += u.w;
                        Dloc[x2+1][y1]     -= u.w;
                        Dloc[x1][y2+1]     -= u.w;
                        Dloc[x2+1][y2+1]   += u.w;
                    }
                }

                // Prefix cục bộ và kiểm tra điều kiện > 1/2
                // Nếu ô nào đã có đáp án khác 0 thì bỏ qua (đã xác định kênh thắng)
                for(int i=1;i<=nx;++i){
                    ll run=0;
                    for(int j=1;j<=ny;++j){
                        run += Dloc[i][j];
                        ll Ec = baseAll + ( (i>1?Dloc[i-1][j]:0) + run ); // Sai! cần prefix 2D chuẩn
                    }
                }
                // prefix 2D chuẩn:
                for(int i=1;i<=nx;++i){
                    for(int j=1;j<=ny;++j){
                        Dloc[i][j] += Dloc[i-1][j] + Dloc[i][j-1] - Dloc[i-1][j-1];
                    }
                }
                bool anySet = false;
                for(int i=1;i<=nx;++i){
                    for(int j=1;j<=ny;++j){
                        int x = xl + i - 1;
                        int y = yl + j - 1;
                        if(ans[x][y]) continue; // đã có kênh thắng
                        ll Ec = baseAll + Dloc[i][j];
                        if( Ec*2 > S[x][y] ){
                            ans[x][y] = t;
                            anySet = true;
                        }
                    }
                }
                // tối ưu nhỏ: nếu tất cả đã gán xong (không có ô nào còn 0 mà có thể được kênh khác thắng >1/2) thì có thể tiếp,
                // nhưng để an toàn ta vẫn thử các ứng viên còn lại.
            }
        }
    }

    // In ra K dòng, mỗi dòng K số
    ff(x,1,K){
        ff(y,1,K){
            if(y>1) cout << ' ';
            cout << ans[x][y];
        }
        cout << '\n';
    }
    return 0;
}