QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #706482 | #1080. Unreal Estate | TheZone | AC ✓ | 1150ms | 16068kb | C++20 | 5.1kb | 2024-11-03 11:39:48 | 2024-11-03 11:39:48 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
struct LL {
LL *pref;
LL *nex;
double val;
int type, id;
LL() {}
LL(double _val, int _type, int _id) : val(_val), type(_type), id(_id) {}
};
struct Event {
double x, y1, y2;
int type, id;
bool operator< (Event e) const {
return x < e.x;
}
};
double licz(LL *start, LL *kon) {
LL *aktu = start->nex;
int cur = 0;
double pop = 0, result = 0;
while (aktu != kon) {
if (aktu->type == 1) {
if (cur == 0)
pop = aktu->val;
cur++;
} else {
cur--;
if (cur == 0) {
result += aktu->val - pop;
}
}
aktu = aktu->nex;
}
return result;
}
void rem(LL *start, LL *kon, int id) {
LL *aktu = start->nex;
while (aktu != kon) {
if (aktu->id == id) {
aktu->pref->nex = aktu->nex;
aktu->nex->pref = aktu->pref;
}
aktu = aktu->nex;
}
}
void add(LL *start, LL *kon, LL *added) {
LL *aktu = start;
while (aktu != kon) {
if (aktu->val < added->val && !(aktu->nex->val < added->val)) {
added->nex = aktu->nex;
added->pref = aktu;
aktu->nex->pref = added;
aktu->nex = added;
break;
}
aktu = aktu->nex;
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n;
cin >> n;
if (n == 0)
break;
vector<Event> events;
for (int i = 0; i < n; i++) {
double x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
events.PB({x1, y1, y2, 1, i});
events.PB({x2, y1, y2, -1, i});
}
sort(all(events));
LL *start = new LL();
LL *kon = new LL();
start->nex = kon;
kon->pref = start;
start->val = -2000;
kon->val = 2000;
double prev = -2000, res = 0;
for (auto event : events) {
res += licz(start, kon) * (event.x - prev);
prev = event.x;
if (event.type == 1) {
LL *add1 = new LL(event.y1, 1, event.id);
LL *add2 = new LL(event.y2, -1, event.id);
add(start, kon, add1);
add(start, kon, add2);
} else {
rem(start, kon, event.id);
}
}
cout << fixed << setprecision(2) << res << "\n";
}
}
/*#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#define rep(i,a,b) for(int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class X, class Y> X cmx(X &a, Y b) { a = max<X>(a, b); }
#define ary(k) array<int, k>
struct LL {
LL *pref;
LL *nex;
double val;
int type, id;
LL() {}
LL(double _val, int _type, int _id) : val(_val), type(_type), id(_id) {}
};
struct Event {
double x, y1, y2;
int type, id;
bool operator< (Event e) const {
return x < e.x;
}
};
double licz(LL *start, LL *kon) {
LL *aktu = start->nex;
int cur = 0;
double pop = 0, result = 0;
while (aktu != kon) {
if (aktu->type == 1) {
if (cur == 0)
pop = aktu->val;
cur++;
} else {
cur--;
if (cur == 0) {
result += aktu->val - pop;
}
}
aktu = aktu->nex;
}
return result;
}
void rem(LL *start, LL *kon, int id) {
LL *aktu = start->nex;
while (aktu != kon) {
if (aktu->id == id) {
aktu->pref->nex = aktu->nex;
aktu->nex->pref = aktu->pref;
}
aktu = aktu->nex;
}
}
void add(LL *start, LL *kon, LL *added) {
LL *aktu = start;
while (aktu != kon) {
if (aktu->val < added->val && !(aktu->nex->val < added->val)) {
added->nex = aktu->nex;
added->pref = aktu;
aktu->nex->pref = added;
aktu->nex = added;
break;
}
aktu = aktu->nex;
}
}
signed main() {
cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
while (true) {
int n;
cin >> n;
if (n == 0)
break;
vector<Event> events;
for (int i = 0; i < n; i++) {
add(start, kon, add2);
} else {
rem(start, kon, event.id);
}
}
cout << fixed << setprecision(2) << res << "\n";
}
}
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1150ms
memory: 16068kb
input:
2 0 0 100 100 30 30 60 60 2 0 100 300 200 100 0 200 300 10 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 0 0 100 100 4000 709.00 143.83 709.25 873.14 331.00 60.72 331.25 893.57 940.50 142.82 940.75 791.43 116.51 48.50 911.15 48.75 980.00 ...
output:
10000.00 50000.00 10000.00 609567.11 808824.16 945654.43 946432.89 944216.15 1000000.00 405000.00 500000.00 594100.00 1000000.00 1000000.00 10000.00 50000.00 10000.00 609567.11 808824.16 945654.43 946432.89 944216.15 1000000.00 405000.00 500000.00 594100.00 1000000.00 1000000.00 10000.00 50000.00 10...
result:
ok 42 lines