oj.uz

Submission #265394

# Submission time Handle Problem Language Result Execution time Memory
265394 2020-08-14T17:59:14 Z TadijaSebez Nuclearia (CEOI15_nuclearia) C++11
30 / 100
 1000 ms 104444 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200050;
int x[N],y[N],a[N],b[N];
int xl[N],xr[N],yl[N],yr[N];
int dist(int x1,int y1,int x2,int y2){return max(abs(x1-x2),abs(y1-y2));}
int get(int i,int X,int Y){return max((ll)0,a[i]-(ll)b[i]*dist(x[i],y[i],X,Y));}
int main(){
	int H,W,n,q;
	scanf("%i %i %i",&H,&W,&n);
	for(int i=1;i<=n;i++)scanf("%i %i %i %i",&x[i],&y[i],&a[i],&b[i]);
	scanf("%i",&q);
	for(int i=1;i<=q;i++)scanf("%i %i %i %i",&xl[i],&yl[i],&xr[i],&yr[i]);
	if(H>W){
		swap(H,W);
		for(int i=1;i<=n;i++)swap(x[i],y[i]);
		for(int i=1;i<=q;i++)swap(xl[i],yl[i]),swap(xr[i],yr[i]);
	}
	vector<ll> fir(W+2,0),add(W+2,0);
	vector<vector<ll>> cell(H+1,vector<ll>(W+1,0));
	for(int i=1;i<=n;i++){
		if(get(i,0,y[i])&&(ll)n*W<=100000000){
			for(int j=1;j<=W;j++)fir[j]+=get(i,0,j);
		}
	}
	for(int i=1;i<=H;i++){
		for(int o=1;o<=n;o++){
			int dif=get(o,i,y[o])-get(o,i-1,y[o]);
			if(dif!=0){
				int rng=i<=x[o]?x[o]-i:i-x[o]-1;
				add[max(1,y[o]-rng)]+=dif;
				add[min(W+1,y[o]+rng+1)]-=dif;
			}
		}
		ll sum=0;
		for(int j=1;j<=W;j++){
			sum+=add[j];
			cell[i][j]=sum+fir[j];
		}
	}
	for(int i=1;i<=H;i++)
		for(int j=1;j<=W;j++)
			cell[i][j]+=cell[i-1][j]+cell[i][j-1]-cell[i-1][j-1];
	for(int i=1;i<=q;i++){
		ll ans=cell[xr[i]][yr[i]]-cell[xl[i]-1][yr[i]]-cell[xr[i]][yl[i]-1]+cell[xl[i]-1][yl[i]-1];
		ll sz=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1);
		ll out=ans/sz;
		if((ans%sz)*2>=sz)out++;
		printf("%lld\n",out);
	}
	return 0;
}

Compilation message

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:11:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   11 |  scanf("%i %i %i",&H,&W,&n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:12:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   12 |  for(int i=1;i<=n;i++)scanf("%i %i %i %i",&x[i],&y[i],&a[i],&b[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   13 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
nuclearia.cpp:14:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |  for(int i=1;i<=q;i++)scanf("%i %i %i %i",&xl[i],&yl[i],&xr[i],&yr[i]);
      |                       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 98168 KB Output is correct
2 Correct 107 ms 5880 KB Output is correct
3 Correct 90 ms 5500 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 98172 KB Output is correct
2 Correct 107 ms 5872 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 20096 KB Output is correct
2 Correct 95 ms 5880 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 23936 KB Output is correct
2 Correct 113 ms 5880 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 101368 KB Output is correct
2 Correct 114 ms 6164 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 606 ms 42616 KB Output is correct
2 Correct 98 ms 5880 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 25720 KB Output is correct
2 Correct 106 ms 6136 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 27000 KB Output is correct
2 Correct 94 ms 5880 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 309 ms 104444 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 314 ms 104440 KB Output isn't correct

Subtask #11
0 / 15.0

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

Subtask #12
0 / 10.0

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

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 611 ms 28760 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

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