| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 130366 |
2019-07-15T04:35:40 Z |
윤교준(#3150) |
Dominance (CEOI08_dominance) |
C++14 |
|
36 ms |
760 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
vector<pii> EV[6005];
int S[2][6005];
int SY[3005], EY[3005], SX[3005], EX[3005];
int A[3005], B[3005], C[3005];
bitset<3005> D;
ll AnsW, AnsB;
int N;
void process() {
vector<int> YV, XV;
for(int i = 0; i < N; i++) {
EY[i]++; EX[i]++;
YV.eb(SY[i]); YV.eb(EY[i]);
XV.eb(SX[i]); XV.eb(EX[i]);
}
sorv(YV); univ(YV);
sorv(XV); univ(XV);
for(int i = 0; i < N; i++) {
SY[i] = int(lower_bound(allv(YV), SY[i]) - YV.begin());
EY[i] = int(lower_bound(allv(YV), EY[i]) - YV.begin());
SX[i] = int(lower_bound(allv(XV), SX[i]) - XV.begin());
EX[i] = int(lower_bound(allv(XV), EX[i]) - XV.begin());
EV[SY[i]].eb(SX[i], D[i] ? 1 : -1);
EV[SY[i]].eb(EX[i], D[i] ? -1 : 1);
EV[EY[i]].eb(SX[i], D[i] ? -1 : 1);
EV[EY[i]].eb(EX[i], D[i] ? 1 : -1);
}
int yn = sz(YV), xn = sz(XV);
memset(S[1], 0, (xn+2)<<2);
for(int y = 0; y < yn; y++) {
memcpy(S[0], S[1], (xn+2)<<2);
memset(S[1], 0, (xn+2)<<2);
for(auto &ev : EV[y]) S[1][ev.first] += ev.second;
for(int x = 1; x < xn; x++) S[1][x] += S[1][x-1];
for(int x = 0; x < xn; x++) {
S[1][x] += S[0][x];
if(S[1][x]) {
ll area = ll(YV[y+1]-YV[y]) * (XV[x+1]-XV[x]);
(0 < S[1][x] ? AnsW : AnsB) += area;
}
}
EV[y].clear();
}
}
int main() {
scanf("%*d%*d%d", &N);
for(int i = 0; i < N; i++) {
char c;
scanf(" %c%d%d%d", &c, &A[i], &B[i], &C[i]);
D[i] = 'W' == c;
}
for(int i = 0; i < N; i++) {
SY[i] = A[i] - C[i] - B[i];
EY[i] = A[i] + C[i] - B[i];
SX[i] = A[i] + B[i] - C[i];
EX[i] = A[i] + B[i] + C[i];
SY[i] = (SY[i] < 0 ? SY[i] : SY[i]+1) / 2;
SX[i] = (SX[i] < 0 ? SX[i] : SX[i]+1) / 2;
EY[i] = (EY[i] < 0 ? EY[i]-1 : EY[i]) / 2;
EX[i] = (EX[i] < 0 ? EX[i]-1 : EX[i]) / 2;
}
process();
for(int i = 0; i < N; i++) {
SY[i] = A[i] - C[i] - B[i];
EY[i] = A[i] + C[i] - B[i];
SX[i] = A[i] + B[i] - C[i];
EX[i] = A[i] + B[i] + C[i];
SY[i] = (SY[i] < 0 ? SY[i]-1 : SY[i]) / 2;
SX[i] = (SX[i] < 0 ? SX[i]-1 : SX[i]) / 2;
EY[i] = (EY[i] < 0 ? EY[i] : EY[i]+1) / 2 - 1;
EX[i] = (EX[i] < 0 ? EX[i] : EX[i]+1) / 2 - 1;
}
process();
cout << AnsW << " " << AnsB << endl;
return 0;
}
Compilation message
dominance.cpp: In function 'int main()':
dominance.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%*d%*d%d", &N);
~~~~~^~~~~~~~~~~~~~~~
dominance.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c%d%d%d", &c, &A[i], &B[i], &C[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
760 KB |
Output is correct |
| 2 |
Correct |
3 ms |
508 KB |
Output is correct |
| 3 |
Correct |
4 ms |
504 KB |
Output is correct |
| 4 |
Correct |
26 ms |
760 KB |
Output is correct |
| 5 |
Correct |
32 ms |
632 KB |
Output is correct |
| 6 |
Correct |
2 ms |
504 KB |
Output is correct |
| 7 |
Correct |
2 ms |
504 KB |
Output is correct |
| 8 |
Correct |
16 ms |
632 KB |
Output is correct |
| 9 |
Correct |
26 ms |
632 KB |
Output is correct |
| 10 |
Correct |
31 ms |
632 KB |
Output is correct |
| 11 |
Correct |
35 ms |
632 KB |
Output is correct |
| 12 |
Correct |
2 ms |
504 KB |
Output is correct |
| 13 |
Correct |
36 ms |
720 KB |
Output is correct |
| 14 |
Correct |
2 ms |
632 KB |
Output is correct |
| 15 |
Correct |
17 ms |
632 KB |
Output is correct |
| 16 |
Correct |
8 ms |
632 KB |
Output is correct |
| 17 |
Correct |
2 ms |
504 KB |
Output is correct |
| 18 |
Correct |
4 ms |
508 KB |
Output is correct |
| 19 |
Correct |
3 ms |
632 KB |
Output is correct |
| 20 |
Correct |
5 ms |
504 KB |
Output is correct |
