| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130401 |
2019-07-15T06:44:19 Z |
송준혁(#3152) |
Dominance (CEOI08_dominance) |
C++14 |
|
18 ms |
632 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
int N;
LL W, B;
LL X[3030], Y[3030], R[3030], C[3030], cnt[6060];
vector<LL> Ocom, Ecom;
struct Data{
LL x, y1, y2, v;
bool operator<(const Data &r)const{
return x < r.x;
}
};
vector<Data> V;
inline int ocomp(LL k){return lower_bound(Ocom.begin(), Ocom.end(), k)-Ocom.begin();}
inline int ecomp(LL k){return lower_bound(Ecom.begin(), Ecom.end(), k)-Ecom.begin();}
int main(){
scanf("%*d %*d");
scanf("%d", &N);
for (int i=1; i<=N; i++){
char ch;
scanf(" %c %lld %lld %lld", &ch, &X[i], &Y[i], &R[i]);
if (ch == 'W') C[i] = 1;
else C[i] = -1;
if ((X[i]+Y[i]+R[i]) & 1){
Ocom.push_back(X[i]+Y[i]-R[i]);
Ocom.push_back(X[i]+Y[i]+R[i]+2);
Ecom.push_back(X[i]+Y[i]-R[i]+1);
Ecom.push_back(X[i]+Y[i]+R[i]+1);
}
else{
Ecom.push_back(X[i]+Y[i]-R[i]);
Ecom.push_back(X[i]+Y[i]+R[i]+2);
Ocom.push_back(X[i]+Y[i]-R[i]+1);
Ocom.push_back(X[i]+Y[i]+R[i]+1);
}
}
sort(Ocom.begin(), Ocom.end());
Ocom.erase(unique(Ocom.begin(), Ocom.end()), Ocom.end());
sort(Ecom.begin(), Ecom.end());
Ecom.erase(unique(Ecom.begin(), Ecom.end()), Ecom.end());
for (int i=1; i<=N; i++){
if ((X[i]+Y[i]+R[i]) & 1){
V.push_back((Data){X[i]-Y[i]-R[i], ocomp(X[i]+Y[i]-R[i]), ocomp(X[i]+Y[i]+R[i]+2), C[i]});
V.push_back((Data){X[i]-Y[i]+R[i]+2, ocomp(X[i]+Y[i]-R[i]), ocomp(X[i]+Y[i]+R[i]+2), -C[i]});
}
else{
V.push_back((Data){X[i]-Y[i]-R[i]+1, ocomp(X[i]+Y[i]-R[i]+1), ocomp(X[i]+Y[i]+R[i]+1), C[i]});
V.push_back((Data){X[i]-Y[i]+R[i]+1, ocomp(X[i]+Y[i]-R[i]+1), ocomp(X[i]+Y[i]+R[i]+1), -C[i]});
}
}
sort(V.begin(), V.end());
for (int i=0; i<(int)V.size(); i++){
if (i > 0){
for (int j=0; j<(int)Ocom.size()-1; j++){
if (cnt[j] > 0) W += ((Ocom[j+1]-Ocom[j])/2) * ((V[i].x-V[i-1].x)/2);
if (cnt[j] < 0) B += ((Ocom[j+1]-Ocom[j])/2) * ((V[i].x-V[i-1].x)/2);
}
}
for (int j=V[i].y1; j<V[i].y2; j++) cnt[j] += V[i].v;
}
memset(cnt, 0, sizeof cnt);
V.clear();
for (int i=1; i<=N; i++){
if ((X[i]+Y[i]+R[i]) & 1){
V.push_back((Data){X[i]-Y[i]-R[i]+1, ecomp(X[i]+Y[i]-R[i]+1), ecomp(X[i]+Y[i]+R[i]+1), C[i]});
V.push_back((Data){X[i]-Y[i]+R[i]+1, ecomp(X[i]+Y[i]-R[i]+1), ecomp(X[i]+Y[i]+R[i]+1), -C[i]});
}
else{
V.push_back((Data){X[i]-Y[i]-R[i], ecomp(X[i]+Y[i]-R[i]), ecomp(X[i]+Y[i]+R[i]+2), C[i]});
V.push_back((Data){X[i]-Y[i]+R[i]+2, ecomp(X[i]+Y[i]-R[i]), ecomp(X[i]+Y[i]+R[i]+2), -C[i]});
}
}
sort(V.begin(), V.end());
for (int i=0; i<(int)V.size(); i++){
if (i > 0){
for (int j=0; j<(int)Ecom.size()-1; j++){
if (cnt[j] > 0) W += ((Ecom[j+1]-Ecom[j])/2) * ((V[i].x-V[i-1].x)/2);
if (cnt[j] < 0) B += ((Ecom[j+1]-Ecom[j])/2) * ((V[i].x-V[i-1].x)/2);
}
}
for (int j=V[i].y1; j<V[i].y2; j++) cnt[j] += V[i].v;
}
printf("%lld %lld\n", W, B);
return 0;
}
Compilation message
dominance.cpp: In function 'int main()':
dominance.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%*d %*d");
~~~~~^~~~~~~~~~~
dominance.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
dominance.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c %lld %lld %lld", &ch, &X[i], &Y[i], &R[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
604 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
504 KB |
Output is correct |
| 4 |
Correct |
7 ms |
632 KB |
Output is correct |
| 5 |
Correct |
9 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Correct |
6 ms |
504 KB |
Output is correct |
| 9 |
Correct |
11 ms |
632 KB |
Output is correct |
| 10 |
Correct |
13 ms |
504 KB |
Output is correct |
| 11 |
Correct |
13 ms |
504 KB |
Output is correct |
| 12 |
Correct |
2 ms |
376 KB |
Output is correct |
| 13 |
Correct |
10 ms |
504 KB |
Output is correct |
| 14 |
Correct |
2 ms |
376 KB |
Output is correct |
| 15 |
Correct |
18 ms |
632 KB |
Output is correct |
| 16 |
Correct |
11 ms |
632 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
3 ms |
376 KB |
Output is correct |
| 19 |
Correct |
4 ms |
504 KB |
Output is correct |
| 20 |
Correct |
4 ms |
376 KB |
Output is correct |
