답안 #777453

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