Submission #1258295

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258295		Zbyszek99	Nuclearia (CEOI15_nuclearia)	C++20	67 / 100	1108 ms	203988 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) 
{
    forall(it,nucs) 
    {
        int x = it.x;
        int y = it.y;
        ll a = it.a;
        ll b = it.b;
        int dist = a/b;

        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;
            }
        }
    }

    rep(x,m) 
    {
        rep(y,n) 
        {
            int idx = y*m + x;
            if(x != 0) 
            {
                pref[0][idx] = pref[0][y*m + (x-1)];
                pref[1][idx] = pref[1][y*m + (x-1)];
                if(y != 0) 
                {
                    dig_up[0][idx] += dig_up[0][(y-1)*m + (x-1)];
                    dig_up[1][idx] += dig_up[1][(y-1)*m + (x-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][(y+1)*m + (x-1)];
                dig_down[1][idx] += dig_down[1][(y+1)*m + (x-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][(y-1)*m + x];
                x_dif[1][idx] += x_dif[1][(y-1)*m + x];
            }
            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,4-d) 
            {
                poz = rotate_point(poz.ff,poz.ss);
                swap(n,m);
            }
            ans[poz.ss][poz.ff] += pref[0][idx];
            rep(kk,d) 
            {
                swap(n,m);
            }
        }
    }

    rep(idx,n*m)
    {
        rep(d2,2) 
        {
            pref[d2][idx] = 0;
            x_dif[d2][idx] = 0;
            dig_up[d2][idx] = 0;
            dig_down[d2][idx] = 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);
    int k;
    cin >> k;
    rep(i,k)
    {
        int x,y;
        ll a,b;
        cin >> x >> y >> a >> b;
        x--;
        y--;
        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();
    }
    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;
    cin >> q;
    rep(qq,q)
    {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        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: 0 / 8