제출 #1258269

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1258269		Zbyszek99	Nuclearia (CEOI15_nuclearia)	C++20	4 / 100	1134 ms	944476 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];
ll** dig_down[2];
ll** x_dif[2];
ll** pref[2];
ll** val_sum;


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

void dealoc(ll*** t)
{
    rep(i,n+2) delete[] (*t)[i];
    delete[] (*t);
}

vector<nuc> nucs;

ll** pom;

void rotate_table(ll*** t)
{
    pom = new ll*[n+2];
    rep(i,n+2) pom[i] = new ll[m+2];
    rep(i,n+2) rep(j,m+2) pom[i][j] = (*t)[i][j];    
    rep(i,n+2) delete[] (*t)[i];
    delete[] (*t);
    (*t) = new ll*[m+2];
    rep(i,m+2) (*t)[i] = new ll[n+2];
    rep(i,n+2)
    {
        rep(j,m+2)
        {
            (*t)[(m+1)-j][i] = pom[i][j];
        }
    }
    rep(i,n+2) delete[] pom[i];
    delete[] pom;
}

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;
    }
    rotate_table(&ans);
    swap(n,m);
}

void solve()
{
    rep(d,2)
    {
        aloc(&dig_down[d]);
        aloc(&dig_up[d]);
        aloc(&pref[d]);
        aloc(&x_dif[d]);
    }
    forall(it,nucs)
    {
        int x = it.x;
        int y = it.y;
        ll a = it.a;
        ll b = it.b;
        int d = a/b;
        dig_up[0][y+1][x+1] += a;
        dig_up[1][y+1][x+1] += -b;
        int d2 = min({(n+1)-y,d+1,(m+1)-x});
        dig_up[0][y+d2][x+d2] += -(a-(d2-1)*b);
        dig_up[1][y+d2][x+d2] += b;
        
        dig_down[0][y][x+1] += a;
        dig_down[1][y][x+1] += -b;
        d2 = min({y,d,(m+1)-(x+1)});
        dig_down[0][y-d2][x+1+d2] += -(a-d*b);
        dig_down[1][y-d2][x+1+d2] += b;
        int yl = max(1,y-d+1);
        int yr = min(n,y+d);
        if(x+d+1 <= m)
        {
            x_dif[0][yl][x+d+1] += -(a-d*b);
            x_dif[1][yl][x+d+1] += b;
            x_dif[0][yr+1][x+d+1] += (a-d*b);
            x_dif[1][yr+1][x+d+1] += -b;
        }
    }
    rep2(x,1,m)
    {
        rep2(y,1,n)
        {
            pref[0][y][x] = pref[0][y][x-1];
            pref[1][y][x] = pref[1][y][x-1];
            dig_up[0][y][x] += dig_up[0][y-1][x-1];
            dig_up[1][y][x] += dig_up[1][y-1][x-1];
            pref[0][y][x] += dig_up[0][y][x];
            pref[1][y][x] += dig_up[1][y][x];
            dig_up[0][y][x] += dig_up[1][y][x];
            dig_down[0][y][x] += dig_down[0][y+1][x-1];
            dig_down[1][y][x] += dig_down[1][y+1][x-1];
            pref[0][y][x] += dig_down[0][y][x];
            pref[1][y][x] += dig_down[1][y][x];
            dig_down[0][y][x] += dig_down[1][y][x];
            x_dif[0][y][x] += x_dif[0][y-1][x];
            x_dif[1][y][x] += x_dif[1][y-1][x];
            pref[0][y][x] += x_dif[0][y][x];
            pref[1][y][x] += x_dif[1][y][x];
            pref[0][y][x] += pref[1][y][x];
            ans[y][x] += pref[0][y][x];
        }
    }
    rep(d,2)
    {
        dealoc(&dig_down[d]);
        dealoc(&dig_up[d]);
        dealoc(&pref[d]);
        dealoc(&x_dif[d]);
    }
}

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

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