Submission #813418

#	Time	Username	Problem	Language	Result	Execution time	Memory
813418		JakobZorz	Nuclearia (CEOI15_nuclearia)	C++14	0 / 100	1076 ms	52408 KiB

nuclearia

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <stack>
#include <limits.h>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <cstring>
#include <sstream>
 
#pragma GCC target("popcnt")
 
typedef long long ll;
typedef long double ld;
using namespace std;
const int MOD=1e9+7;
typedef pair<ll,ll>point;
//#define x first
//#define y second

int w,h;

class Matrix{
    vector<ll>map_arr;
public:
    void init_map(){
        map_arr.resize(w*h);
    }

    ll get2(int x,int y){
        if(x<0||y<0)
            return 0;
        return map_arr[y*w+x];
    }

    ll&get(int x,int y){
        return map_arr[y*w+x];
    }

    void add_bounded(int x,int y,ll val){
        if(x<0)
            x=0;
        if(y<0)
            y=0;
        if(x>=w)
            return;
        if(y>=h)
            return;
        get(x,y)+=val;
    }
};
 
Matrix mat;

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>w>>h;
    mat.init_map();
    int n;
    cin>>n;
    while(n--){
        int x1,y1;
        ll center,step;
        cin>>x1>>y1>>center>>step;
        x1--;y1--;
        
        ll last_step=(center-1)%step+1;
        int num_steps=(int)(center+step-1)/step;
        
        if(x1>y1){
            // hits ceiling
            for(int i=0;i<num_steps-1;i++)
                mat.add_bounded(x1-i,y1-i,step);
            /*for(int i=0;i<num_steps-1&&i<y1;i++)
                mat.get(x1-i,y1-i)+=step;
            
            for(int i=y1;i<num_steps-1&&i<x1;i++)
                mat.get(x1-i,0)+=step;
            
            for(int i=x1;i<num_steps-1;i++)
                mat.get(0,0)+=step;*/
        }else{
            for(int i=0;i<num_steps-1;i++)
                mat.add_bounded(x1-i,y1-i,step);
            // hits left wall
            /*for(int i=0;i<num_steps-1&&i<x1;i++)
                mat.get(x1-i,y1-i)+=step;
            
            for(int i=x1;i<num_steps-1&&i<y1;i++)
                mat.get(0,y1-i)+=step;
            
            for(int i=y1;i<num_steps-1;i++)
                mat.get(0,0)+=step;*/
        }
        
        for(int i=0;i<num_steps-1;i++){
            mat.add_bounded(x1-i,y1+i+1,-step);
        }
        
        for(int i=0;i<num_steps-1;i++){
            mat.add_bounded(x1+i+1,y1-i,-step);
        }
        
        for(int i=0;i<num_steps-1;i++)
            mat.add_bounded(x1+i+1,y1+i+1,step);
        
        mat.add_bounded(x1-num_steps+1, y1-num_steps+1, last_step);
        mat.add_bounded(x1-num_steps+1, y1+num_steps,   -last_step);
        mat.add_bounded(x1+num_steps,   y1-num_steps+1, -last_step);
        mat.add_bounded(x1+num_steps,   y1+num_steps,   last_step);
        
        /*for(int x=0;x<w;x++)
            for(int y=0;y<h;y++){
                int dist=max(abs(x1-x),abs(y1-y));
                ll val=max(0LL,center-dist*step);
                get(x,y)+=val;
            }*/
    }
    
    for(int x=0;x<w;x++)
        for(int y=0;y<h;y++)
            mat.get(x,y)+=mat.get2(x-1,y)+mat.get2(x,y-1)-mat.get2(x-1,y-1);
    
    for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            cout<<mat.get(x,y)<<" ";
        }
        cout<<"\n";
    }
    
    for(int x=0;x<w;x++)
        for(int y=0;y<h;y++)
            mat.get(x,y)+=mat.get2(x-1,y)+mat.get2(x,y-1)-mat.get2(x-1,y-1);
    
    int q;
    cin>>q;
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        x1--;y1--;
        
        ll sum=mat.get2(x2-1,y2-1)+mat.get2(x1-1,y1-1)-mat.get2(x1-1,y2-1)-mat.get2(x2-1,y1-1);
        
        ll area=(x2-x1)*(y2-y1);
        ll res=sum/area;
        if((sum%area)*2>=area)
            res++;
        cout<<res<<"\n";
    }

    return 0;
}

/*

4 3
2
1 1 7 3
3 2 4 2
4
1 2 2 3
1 1 4 3
4 2 4 2
1 3 4 3

*/

• 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: 0 / 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