oj.uz

Submission #265416

# Submission time Handle Problem Language Result Execution time Memory
265416 2020-08-14T19:21:10 Z TadijaSebez Nuclearia (CEOI15_nuclearia) C++11
67 / 100
 1000 ms 247228 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma comment(linker, "/stack:200000000")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200050;
int x[N],y[N],a[N],b[N],rng[N];
int xl[N],xr[N],yl[N],yr[N];
inline int dist(int x1,int y1,int x2,int y2){return max(abs(x1-x2),abs(y1-y2));}
inline 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(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int H,W,n,q;
	cin>>H>>W>>n;
	for(int i=1;i<=n;++i)cin>>x[i]>>y[i]>>a[i]>>b[i],rng[i]=a[i]/b[i];
	cin>>q;
	for(int i=1;i<=q;++i)cin>>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),f_d(W+2,0),f_n(W+2,0);
	vector<vector<ll>> cell(H,vector<ll>(W,0)),add_d1(H+2,vector<ll>(W+2,0)),add_d2(H+2,vector<ll>(W+2,0));
	auto get_t=[&](int o,int i){return i<=x[o]?x[o]-i:i-x[o]-1;};
	for(int i=1;i<=n;++i){
		if(x[i]<=rng[i]){
			int t=get_t(i,0);
			int val=get(i,0,y[i]);
			if(y[i]-t-1>=1){
				f_d[max(1,y[i]-rng[i])]+=b[i];
				f_d[y[i]-t]-=b[i];
				f_n[max(1,y[i]-rng[i])]+=val-(ll)(y[i]-t)*b[i];
				f_n[y[i]-t]-=val-(ll)(y[i]-t)*b[i];
			}
			f_n[max(1,y[i]-t)]+=val;
			f_n[min(W+1,y[i]+t+1)]-=val;
			if(y[i]+t+1<=W){
				f_d[y[i]+t+1]-=b[i];
				f_d[min(W+1,y[i]+rng[i]+1)]+=b[i];
				f_n[y[i]+t+1]+=val+(ll)(y[i]+t)*b[i];
				f_n[min(W+1,y[i]+rng[i]+1)]-=val+(ll)(y[i]+t)*b[i];
			}
		}
	}
	for(int i=1;i<=W;i++){
		f_n[i]+=f_n[i-1];
		f_d[i]+=f_d[i-1];
		fir[i]=f_n[i]+f_d[i]*i;
	}
	for(int i=1;i<=H;++i){
		for(int o=1;o<=n;++o){
			int t=get_t(o,i);
			if(t<=rng[o]){
				int dif=t==rng[o]?get(o,i,y[o])-get(o,i-1,y[o]):(i<=x[o]?b[o]:-b[o]);
				add[max(1,y[o]-t)]+=dif;
				add[min(W+1,y[o]+t+1)]-=dif;
			}
		}
		ll sum=0;
		for(int j=1;j<=W;++j){
			sum+=add[j];
			cell[i-1][j-1]=sum+fir[j];
			//printf("%lld ",sum+fir[j]);
			cell[i-1][j-1]+=(i!=1?cell[i-2][j-1]:0)+(j!=1?cell[i-1][j-2]:0)-(i!=1&&j!=1?cell[i-2][j-2]:0);
		}
		//printf("\n");
	}
	for(int i=1;i<=q;++i){
		ll ans=cell[xr[i]-1][yr[i]-1]-(xl[i]!=1?cell[xl[i]-2][yr[i]-1]:0)-(yl[i]!=1?cell[xr[i]-1][yl[i]-2]:0)+(xl[i]!=1&&yl[i]!=1?cell[xl[i]-2][yl[i]-2]:0);
		ll sz=(xr[i]-xl[i]+1)*(yr[i]-yl[i]+1);
		ll out=ans/sz;
		if((ans%sz)*2>=sz)out++;
		cout<<out<<"\n";
	}
	return 0;
}

Compilation message

nuclearia.cpp:3: warning: ignoring #pragma comment  [-Wunknown-pragmas]
    3 | #pragma comment(linker, "/stack:200000000")
      |

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 235276 KB Output is correct
2 Correct 81 ms 7800 KB Output is correct
3 Correct 73 ms 7032 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 235276 KB Output is correct
2 Correct 83 ms 7928 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 59512 KB Output is correct
2 Correct 78 ms 7544 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 68004 KB Output is correct
2 Correct 83 ms 7832 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 242988 KB Output is correct
2 Correct 91 ms 8568 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 102420 KB Output is correct
2 Correct 85 ms 7800 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 67704 KB Output is correct
2 Correct 85 ms 8184 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 67248 KB Output is correct
2 Correct 77 ms 7604 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 247228 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 247180 KB Output is correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 834 ms 70924 KB Output is correct
2 Execution timed out 1098 ms 68896 KB Time limit exceeded

Subtask #12
0 / 10.0

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

Subtask #13
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 72792 KB Output is correct
2 Correct 636 ms 76280 KB Output is correct

Subtask #14
0 / 8.0

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