제출 #1258322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258322		Zbyszek99	Nuclearia (CEOI15_nuclearia)	C++17	75 / 100	1107 ms	367272 KiB

nuclearia

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

struct nuc
{
    int x,y;
    ll a,b;
};

int n,m;
ll** ans;
ll dig_up[2][25000001];
ll dig_down[2][25000001];
ll x_dif[2][25000001];
ll pref[2][25000001];
ll** val_sum;


void aloc(ll*** t)
{
    *t = new ll*[n];
    rep(i,n) (*t)[i] = new ll[m];
    rep(i,n)
    {
        rep(j,m)
        {
            (*t)[i][j] = 0;
        }
    }
}

vector<nuc> nucs;

pii rotate_point(int x, int y)
{
    return {y,(m-1)-x};
}

void rotate_all()
{
    rep(i,siz(nucs))
    {
        pii poz = rotate_point(nucs[i].x,nucs[i].y);
        nucs[i].x = poz.ff;
        nucs[i].y = poz.ss;
    }
    swap(n,m);
}

void solve(int d) 
{
    int minx = 1e9;
    int maxx = -1e9;
    int miny = 1e9;
    int maxy = -1e9;
    forall(it,nucs) 
    {
        int x = it.x;
        int y = it.y;
        ll a = it.a;
        ll b = it.b;
        int dist = a/b;
        minx = min(minx,x);
        maxx = max(maxx,x+dist);
        miny = min(miny,y-dist);
        maxy = max(maxy,y+dist);
        if(y != n-1 && x != m-1) 
        {
            dig_up[0][ (y+1)*m + (x+1) ] += a;
            dig_up[1][ (y+1)*m + (x+1) ] += -b;
        }
        int d2 = dist+1;
        if(y+d2 < n && x+d2 < m) 
        {
            dig_up[0][ (y+d2)*m + (x+d2) ] += -(a-(d2-1)*b);
            dig_up[1][ (y+d2)*m + (x+d2) ] += b;
        }
        if(x != m-1) 
        {
            dig_down[0][ y*m + (x+1) ] += a;
            dig_down[1][ y*m + (x+1) ] += -b;
        }
        d2 = dist;
        if(y-d2 >= 0 && x+1+d2 < m) 
        {
            dig_down[0][ (y-d2)*m + (x+1+d2) ] += -(a-dist*b);
            dig_down[1][ (y-d2)*m + (x+1+d2) ] += b;
        }
        int yl = max(0,y-dist+1);
        int yr = min(n-1,y+dist);
        if(x+dist+1 < m) 
        {
            x_dif[0][ yl*m + (x+dist+1) ] += -(a-dist*b);
            x_dif[1][ yl*m + (x+dist+1) ] += b;
            if(yr != n-1) 
            {
                x_dif[0][ (yr+1)*m + (x+dist+1) ] += (a-dist*b);
                x_dif[1][ (yr+1)*m + (x+dist+1) ] += -b;
            }
        }
    }
    maxx = min(maxx,m-1);
    minx = max(minx,0);
    maxy = min(maxy,n-1);
    miny = max(miny,0);
    int xd = (4-d)%4;
    int idx = miny*m+minx;
    rep2(x,minx,maxx)
    {
        rep2(y,miny,maxy)
        {
            if(x != 0) 
            {
                pref[0][idx] = pref[0][idx-1];
                pref[1][idx] = pref[1][idx-1];
                if(y != 0) 
                {
                    dig_up[0][idx] += dig_up[0][idx-m-1];
                    dig_up[1][idx] += dig_up[1][idx-m-1];
                }
            }
            pref[0][idx] += dig_up[0][idx];
            pref[1][idx] += dig_up[1][idx];
            dig_up[0][idx] += dig_up[1][idx];
            if(y != n-1 && x != 0) 
            {
                dig_down[0][idx] += dig_down[0][idx+m-1];
                dig_down[1][idx] += dig_down[1][idx+m-1];
            }
            pref[0][idx] += dig_down[0][idx];
            pref[1][idx] += dig_down[1][idx];
            dig_down[0][idx] += dig_down[1][idx];
            if(y != 0) 
            {
                x_dif[0][idx] += x_dif[0][idx-m];
                x_dif[1][idx] += x_dif[1][idx-m];
            }
            pref[0][idx] += x_dif[0][idx];
            pref[1][idx] += x_dif[1][idx];
            pref[0][idx] += pref[1][idx];
            pii poz = {x,y};
            rep(kk,xd) 
            {
                poz = rotate_point(poz.ff,poz.ss);
                swap(n,m);
            }
            ans[poz.ss][poz.ff] += pref[0][idx];
            rep(kk,d) 
            {
                swap(n,m);
            }
            if(x > 1)
            {
                rep(d,2)
                {
                    pref[d][idx-2] = 0;
                    x_dif[d][idx-2] = 0;
                    dig_up[d][idx-2] = 0;
                    dig_down[d][idx-2] = 0;
                }
            }
            idx+=m;
        }
        idx -= m*(maxy-miny+1);
        idx++;
    }
    rep(i,n) 
    {
        rep2(j,max(0,maxx-1),maxx) 
        {
            int idx = i*m + j;
            rep(d2,2) 
            {
                pref[d2][idx] = 0;
                x_dif[d2][idx] = 0;
                dig_up[d2][idx] = 0;
                dig_down[d2][idx] = 0;
            }
        }
    }
}

const int BUFFER_SIZE = 1 << 24;
char buf[BUFFER_SIZE];
int buf_pos = 0, buf_len = 0;

inline char nextChar() {
    if (buf_pos == buf_len) {
        buf_len = fread(buf, 1, BUFFER_SIZE, stdin);
        buf_pos = 0;
        if (buf_len == 0) return EOF;
    }
    return buf[buf_pos++];
}

inline int fastInt() {
    int x = 0;
    char c = nextChar();
    bool neg = false;
    while ((c < '0' || c > '9') && c != EOF) {
        if (c == '-') neg = true;
        c = nextChar();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = nextChar();
    }
    return neg ? -x : x;
}


int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    m = fastInt();
    n = fastInt();
    aloc(&ans);
    aloc(&val_sum);
    int k = fastInt();
    rep(i,k)
    {
        int x = fastInt();
        int y = fastInt();
        ll a = fastInt();
        ll b = fastInt();
        
        x--;
        y--;
        int d = a/b;
        if(d <= 12)
        {
            rep2(x2,max(0,x-d),min(m-1,x+d))
            {
                rep2(y2,max(0,y-d),min(n-1,y+d))
                {
                    ans[y2][x2] += max(0LL,a-max(abs(x2-x),abs(y2-y))*b);
                }
            }
            continue;
        }
        ans[y][x] += a;
        nucs.pb({x,y,a,b});
    }
    rep(kk,4)
    {
        solve(kk);
        rotate_all();
    }
    rep(i,n)
    {
        rep(j,m)
        {
            val_sum[i][j] = ans[i][j];
            if(i != 0) val_sum[i][j] += val_sum[i-1][j];
            if(j != 0) val_sum[i][j] += val_sum[i][j-1];
            if(i != 0 && j != 0) val_sum[i][j] -= val_sum[i-1][j-1];
        }
    }
    int q = fastInt();
    rep(qq,q)
    {
        int x1 = fastInt(),y1 = fastInt(),x2 = fastInt(),y2 = fastInt();
        x1--;
        y1--;
        x2--;
        y2--;
        ld sum = (val_sum[y2][x2]-(y1 != 0 ? val_sum[y1-1][x2] : 0)-(x1 != 0 ? val_sum[y2][x1-1] : 0) + (y1 != 0 && x1 != 0 ? val_sum[y1-1][x1-1] : 0))/(ld)((x2-x1+1)*(y2-y1+1));
        ll ans = sum;
        sum -= ans;
        if(sum >= 0.5) ans++;
        cout << ans << "\n";
    }
}

• Subtask 1: 3 / 3
• Subtask 2: 2 / 2
• Subtask 3: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 6 / 6
• Subtask 6: 4 / 4
• Subtask 7: 6 / 6
• Subtask 8: 4 / 4
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10
• Subtask 11: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 12 / 12
• Subtask 14: 8 / 8