답안 #777453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
777453	2023-07-09T09:16:02 Z	vjudge1	NLO (COCI18_nlo)	C++17	110 / 110	253 ms	11732 KB

nlo

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+37;
#define int long long
vector<int> s(N), v(N);
int mat[10][10];
		
void f(){
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
}

 
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
 
//	f();	
	int n, m, p; cin >> n >> m >> p;
 	
 	for(auto &i: mat){
 		for(auto &j: i)
 			j=1;
 	}

 		
	vector<array<int, 2>> a[n];
	vector<int> val(n, m);
	int full=n*m;
	int ans=0;

	vector<array<int, 3>> e(p);

	for(int i = 0; i < p; i++){
		cin >> e[i][0] >> e[i][1] >> e[i][2]; 
		e[i][0]--; e[i][1]--;
	}

	reverse(e.begin(), e.end());

	for(int i=0; i<p; i++){
		int left=e[i][1], right=e[i][1];
		int x=e[i][0], y=e[i][1], z=e[i][2];

		for(int j = e[i][0]-e[i][2]; j < e[i][0]+e[i][2]+1; j++){
			//cout<<left<<" "<<right<<"\n";
			vector<array<int, 2>> b;
			a[j].push_back({left, right});
			sort(a[j].begin(), a[j].end());

			int lx=a[j][0][0], rx=a[j][0][1];
			int k=m;

			for(auto i: a[j]){
				if(i[0]-1>rx){	
					b.push_back({lx, rx});
					k-=rx-lx+1;
					lx=i[0], rx=i[1];

				}
				else{
					rx=max(rx, i[1]);
				}
			}	


			b.push_back({lx, rx});
			k-=rx-lx+1;
			full-=val[j];
			full+=k;
			a[j] = b;
			val[j] = k;

				if(j!=e[i][0]+e[i][2]){

				int ty=left-1, tx=j+1;
				int f=(z*z)-((x-tx)*(x-tx));

				while(ty>=0&&(y-ty)*(y-ty)<=f){
					left=ty; ty--;
				}

				ty=left;

				while(ty<m-1&&(y-ty)*(y-ty)>f){
						ty++; left=ty;
				}
				
				ty=right+1;

				while(ty<m&&(y-ty)*(y-ty)<=f){
					right=ty; ty++;
				}
				 
				ty=right;

				while(ty>0&&(y-ty)*(y-ty)>f){
						ty--, right=ty;
				}
				
			}
		}


		ans+=full;
	}
	

	cout<<ans<<"\n";
}

Compilation message

nlo.cpp: In function 'void f()':
nlo.cpp:9:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |  freopen("in.txt", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
nlo.cpp:10:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   10 |  freopen("out.txt", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2004 KB	Output is correct
2	Correct	4 ms	1876 KB	Output is correct
3	Correct	4 ms	2544 KB	Output is correct
4	Correct	16 ms	2488 KB	Output is correct
5	Correct	33 ms	3828 KB	Output is correct
6	Correct	97 ms	5948 KB	Output is correct
7	Correct	62 ms	7388 KB	Output is correct
8	Correct	188 ms	8552 KB	Output is correct
9	Correct	99 ms	11732 KB	Output is correct
10	Correct	253 ms	10428 KB	Output is correct