oj.uz

답안 #813521

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
813521 2023-08-07T19:29:03 Z JakobZorz Nuclearia (CEOI15_nuclearia) C++14
92 / 100
 1000 ms 80904 KB 
#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;
        //if(x>=w||y>=h)
            //assert(false);
        return map_arr[y*w+x];
    }

    ll&get(int x,int y){
        //if(x<0||y<0||x>=w||y>=h)
            //assert(false);
        
        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,mat_diag1,mat_diag2;
vector<ll>hor_vec,ver_vec;

void add_hor_line(int x1,int x2,ll val){
    if(x1>=x2)
        return;
    hor_vec[x1]+=val;
    if(x2<w)
        hor_vec[x2]-=val;
}

void add_ver_line(int y1,int y2,ll val){
    if(y1>=y2)
        return;
    ver_vec[y1]+=val;
    if(y2<h)
        ver_vec[y2]-=val;
}

void add_diagonal1(int x,int y,int l,ll val){
    //cout<<"call: "<<x<<" "<<y<<" "<<l<<" "<<val<<"\n";
    mat_diag1.add_bounded(x,y,val);
    mat_diag1.add_bounded(x+l,y+l,-val);
    //for(int i=0;i<l;i++)
        //mat_diag1.get(x+i,y+i)+=val;
}

void add_diagonal2(int x,int y,int l,ll val){
    for(int i=0;i<l;i++)
        mat_diag2.get(x-i,y+i)+=val;
}

int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>w>>h;
    mat.init_map();
    mat_diag1.init_map();
    mat_diag2.init_map();
    hor_vec.resize(w);
    ver_vec.resize(h);
    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
            add_diagonal1(x1-min(num_steps-1,y1)+1,y1-min(num_steps-1,y1)+1,min(num_steps-1,y1),step);
            
            add_hor_line(x1-min(num_steps-1,x1)+1,x1-y1+1,step);
            
            if(x1<num_steps-1)
                mat.get(0,0)+=step*(num_steps-1-x1);
        }else{
            // hits left wall
            add_diagonal1(x1-min(num_steps-1,x1)+1,y1-min(num_steps-1,x1)+1,min(num_steps-1,x1),step);
            
            add_ver_line(y1-min(num_steps-1,y1)+1,y1-x1+1,step);
            
            if(y1<num_steps-1)
                mat.get(0,0)+=step*(num_steps-1-y1);
        }
        
        if(x1+y1<w){
            // hits ceiling
            for(int i=0;i<min(num_steps-1,y1);i++)
                mat.get(x1+min(num_steps-1,y1)-i,y1-min(num_steps-1,y1)+1+i)-=step;
            
            add_hor_line(y1+x1+1,min(num_steps+x1,w),-step);
            
        }else
            add_diagonal2(x1+min(num_steps-1,w-x1-1),y1-min(num_steps-1,w-x1-1)+1,min(num_steps-1,w-x1-1),-step);
        
        if(x1+y1<h){
            // hits left wall
            add_diagonal2(x1,y1+1,min(num_steps-1,x1),-step);
            
            add_ver_line(x1+y1+1,min(num_steps+y1,h),-step);
            
        }else
            add_diagonal2(x1,y1+1,min(num_steps-1,h-y1-1),-step);
        
        if(w-x1<h-y1)
            add_diagonal1(x1+1,y1+1,min(num_steps-1,w-x1-1),step);
        else
            add_diagonal1(x1+1,y1+1,min(num_steps-1,h-y1-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 i=0;i<w;i++){
        if(i)
            hor_vec[i]+=hor_vec[i-1];
        mat.get(i,0)+=hor_vec[i];
    }
    
    for(int i=0;i<h;i++){
        if(i)
            ver_vec[i]+=ver_vec[i-1];
        mat.get(0,i)+=ver_vec[i];
    }
    
    /*for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            cout<<mat_diag1.get(x,y)<<" ";
        }
        cout<<"\n";
    }*/
    
    for(int y=0;y<h;y++)
        for(int i=1;y+i<h&&i<w;i++)
            mat_diag1.get(i,y+i)+=mat_diag1.get(i-1,y+i-1);
    
    for(int x=1;x<w;x++)
        for(int i=1;x+i<w&&i<h;i++)
            mat_diag1.get(x+i,i)+=mat_diag1.get(x+i-1,i-1);
    
    /*for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            cout<<mat_diag1.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)+mat_diag1.get(x,y)+mat_diag2.get(x,y);
    
    /*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
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 78548 KB Output is correct
2 Correct 45 ms 2708 KB Output is correct
3 Correct 42 ms 2196 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 78488 KB Output is correct
2 Correct 45 ms 2712 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 58964 KB Output is correct
2 Correct 46 ms 2672 KB Output is correct

Subtask #4
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 59996 KB Output is correct
2 Correct 46 ms 2636 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 134 ms 80904 KB Output is correct
2 Correct 49 ms 2892 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 80 ms 33928 KB Output is correct
2 Correct 45 ms 2636 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 187 ms 61488 KB Output is correct
2 Correct 46 ms 2912 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 78 ms 30028 KB Output is correct
2 Correct 45 ms 2636 KB Output is correct

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 209 ms 80896 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 215 ms 80896 KB Output is correct

Subtask #11
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 471 ms 61012 KB Output is correct
2 Correct 634 ms 61412 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 699 ms 61180 KB Output is correct
2 Correct 427 ms 60984 KB Output is correct

Subtask #13
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 61604 KB Output is correct
2 Correct 680 ms 61416 KB Output is correct

Subtask #14
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1030 ms 64832 KB Time limit exceeded
2 Halted 0 ms 0 KB -