| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 873994 |
2023-11-16T07:08:34 Z |
azberjibiou |
None (JOI14_ho_t5) |
C++17 |
|
1 ms |
348 KB |
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<pair<int, int>, pair<int, int>>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=200005;
const int mxM=500004;
const int mxK=30;
const int MOD=1'000'000'007;
const ll INF=8e18;
typedef struct BIT{
int fen[mxN], n;
void set_n(int m){n=m;}
void upd(int idx, int val){for(;idx<=n;idx+=(idx&(-idx))) fen[idx]+=val;}
int sum(int idx){int res=0; for(;idx>0;idx-=(idx&(-idx))) res+=fen[idx]; return res;}
int solv(int s, int e){return sum(e)-sum(s-1);}
}BIT;
typedef struct line{
ll x1, x2, y, xy; ///xy=1: x축과 평행 2: y축과 평행
line() : x1(), x2(), y(), xy() {}
line(ll x1, ll x2, ll y, ll xy) : x1(x1), x2(x2), y(y), xy(xy) {}
}line;
int N;
ll H, W;
vector <line> v;
vector <line> ev;
BIT T1;
ll cntV, cntE;
void input(){
cin >> W >> H >> N;
v.emplace_back(0, W, 0, 1);
v.emplace_back(0, W, H, 1);
v.emplace_back(0, H, 0, 2);
v.emplace_back(0, H, W, 2);
for(int i=1;i<=N;i++){
int a, b, c, d;
cin >> a >> b >> c >> d;
if(a==c) v.emplace_back(b, d, c, 2);
else v.emplace_back(a, c, b, 1);
}
}
void coor_comp(){
vector <ll> crx, cry;
for(auto &[x1, x2, y, xy] : v){
x1=3*x1-1, x2=3*x2+1, y=3*y;
if(xy==1) crx.push_back(x1), crx.push_back(x2), cry.push_back(y);
else cry.push_back(x1), cry.push_back(x2), crx.push_back(y);
}
sort(all(crx));
crx.erase(unique(all(crx)), crx.end());
sort(all(cry));
cry.erase(unique(all(cry)), cry.end());
for(auto &[x1, x2, y, xy] : v){
if(xy==1){
x1=lower_bound(all(crx), x1)-crx.begin()+1;
x2=lower_bound(all(crx), x2)-crx.begin()+1;
y=lower_bound(all(cry), y)-cry.begin()+1;
}
else{
x1=lower_bound(all(cry), x1)-cry.begin()+1;
x2=lower_bound(all(cry), x2)-cry.begin()+1;
y=lower_bound(all(crx), y)-crx.begin()+1;
}
if(xy==1) ev.emplace_back(x1, x2, y, xy);
else ev.emplace_back(y, 1, x1, xy), ev.emplace_back(y, -1, x2, xy);
}
W=crx.size(), H=cry.size();
sort(all(ev), [](line a, line b){return a.y<b.y;});
}
void count_VE(){
T1.set_n(W);
cntV=2*(N+4);
for(auto [x1, x2, y, xy] : ev){
if(xy==1) cntV+=T1.solv(x1, x2);
else T1.upd(x1, x2);
//printf("x1=%d, x2=%d, y=%d, xy=%d\n", x1, x2, y, xy);
}
//2*(N+4)+4*(cntV-2*(N+4))=2*cntE
cntE=2*cntV-3*(N+4);
}
int main()
{
gibon
input();
coor_comp();
count_VE();
//V-E+F=2
printf("cntE=%lld, cntV=%lld\n", cntE, cntV);
cout << cntE-cntV+1;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
