Submission #1258277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258277		Zbyszek99	Nuclearia (CEOI15_nuclearia)	C++20	19 / 100	1113 ms	1114112 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** dig_up2[2];
ll** dig_down2[2];
ll** x_dif2[2];
ll** pref2[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;
        }
    }
}

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(pref,pref2);
    swap(x_dif,x_dif2);
    swap(dig_up,dig_up2);
    swap(dig_down,dig_down2);
    swap(n,m);
}

void solve(int 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];
            pii poz = {x,y};
            rep(kk,4-d)
            {
                poz = rotate_point(poz.ff,poz.ss);
                swap(n,m);
            }
            ans[poz.ss][poz.ff] += pref[0][y][x];
            rep(kk,d)
            {
                swap(n,m);
            }
        }
    }
    rep2(i,1,n)
    {
        rep2(j,1,m)
        {
            rep(d,2)
            {
                pref[d][i][j] = 0;
                x_dif[d][i][j] = 0;
                dig_up[d][i][j] = 0;
                dig_down[d][i][j] = 0;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random_start();
    cin >> m >> n;
    aloc(&ans);
    aloc(&val_sum);
    rep(d,2)
    {
        aloc(&dig_up[d]);
        aloc(&dig_down[d]);
        aloc(&x_dif[d]);
        aloc(&pref[d]);
        swap(n,m);
        aloc(&dig_up2[d]);
        aloc(&dig_down2[d]);
        aloc(&x_dif2[d]);
        aloc(&pref2[d]);
        swap(n,m);
    }
    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(kk);
        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: 3 / 3
• Subtask 4: 2 / 2
• Subtask 5: 0 / 6
• Subtask 6: 4 / 4
• Subtask 7: 6 / 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