oj.uz

Submission #813355

# Submission time Handle Problem Language Result Execution time Memory
813355 2023-08-07T16:18:19 Z JakobZorz Nuclearia (CEOI15_nuclearia) C++14
40 / 100
 1000 ms 29220 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

vector<ll>map_arr;
int w,h;

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;
}
 
int main(){
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    cin>>w>>h;
    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;
        ll num_steps=(center+step-1)/step;
        
        for(int i=0;i<num_steps;i++){
            ll val=step;
            if(i==num_steps-1)
                val=last_step;
            add_bounded(x1-i,y1-i,val);
            add_bounded(x1-i,y1+i+1,-val);
            add_bounded(x1+i+1,y1-i,-val);
            add_bounded(x1+i+1,y1+i+1,val);
        }
        
        /*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++)
            get(x,y)+=get2(x-1,y)+get2(x,y-1)-get2(x-1,y-1);
    
    /*for(int y=0;y<h;y++){
        for(int x=0;x<w;x++){
            cout<<get(x,y)<<" ";
        }
        cout<<"\n";
    }*/
    
    for(int x=0;x<w;x++)
        for(int y=0;y<h;y++)
            get(x,y)+=get2(x-1,y)+get2(x,y-1)-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=get2(x2-1,y2-1)+get2(x1-1,y1-1)-get2(x1-1,y2-1)-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

# Verdict Execution time Memory Grader output
1 Correct 296 ms 19796 KB Output is correct
2 Correct 48 ms 4256 KB Output is correct
3 Correct 44 ms 3788 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 19796 KB Output is correct
2 Correct 48 ms 4008 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 19796 KB Output is correct
2 Correct 51 ms 4016 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 19808 KB Output is correct
2 Correct 54 ms 4128 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 157 ms 23496 KB Output is correct
2 Correct 57 ms 4736 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 12032 KB Output is correct
2 Correct 60 ms 4424 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 23656 KB Output is correct
2 Correct 50 ms 4692 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 12028 KB Output is correct
2 Correct 47 ms 4244 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1071 ms 19796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 19796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 24028 KB Output is correct
2 Execution timed out 1068 ms 26784 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 956 ms 24064 KB Output is correct
2 Correct 513 ms 29220 KB Output is correct

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 20120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 20412 KB Time limit exceeded
2 Halted 0 ms 0 KB -