QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#856219 | #3938. Gameworld Tornado | WeaRD276 | AC ✓ | 391ms | 49472kb | C++20 | 2.6kb | 2025-01-13 19:03:06 | 2025-01-13 19:03:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define x first
#define y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
typedef long long ll;
typedef double db;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<db, db> pdd;
typedef pair<ll, ll> pll;
struct SegTree
{
int n;
vector<ll> cnt, sm;
vector<ll> am;
SegTree(int _n, const vector<ll>& _am)
{
n = _n;
cnt.assign(4 * n, 0);
sm.assign(4 * n, 0);
am = _am;
}
void update(int v, int st, int en, int l, int r, int del)
{
if (st > r || en < l)
return;
if (st >= l && en <= r)
{
cnt[v] += del;
}
else
{
int mid = (st + en) / 2;
update(2 * v, st, mid, l, r, del);
update(2 * v + 1, mid + 1, en, l, r, del);
}
if (cnt[v] > 0)
{
sm[v] = am[en + 1] - am[st];
}
else if (st == en)
{
sm[v] = 0;
}
else
{
sm[v] = sm[2 * v] + sm[2 * v + 1];
}
}
ll query()
{
return sm[1];
}
};
struct Event
{
ll x, y1, y2;
int del;
Event(ll _x, ll _y1, ll _y2, int _del) : x(_x), y1(_y1), y2(_y2), del(_del) {}
bool operator<(const Event& oth)
{
if (this->x == oth.x)
{
return this->del > oth.del;
}
return this->x < oth.x;
}
};
int solve()
{
int n;
if (!(cin >> n))
return 1;
vector<Event> a;
set<ll> ys;
FOR (i, 0, n)
{
ll x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
a.pb(Event(x1, y1, y2, 1));
a.pb(Event(x2, y1, y2, -1));
ys.insert(y1);
ys.insert(y2);
}
sort(all(a));
int j = 0;
map<ll, int> m;
for (ll el: ys)
m[el] = j++;
FOR (i, 0, sz(a))
{
a[i].y1 = m[a[i].y1];
a[i].y2 = m[a[i].y2];
}
vector<ll> am;
for (auto [key, val]: m)
am.pb(key);
int nn = sz(ys);
SegTree st(nn, am);
ll ans = 0;
ll prX = a[0].x;
FOR (i, 0, sz(a))
{
ll x = a[i].x, y1 = a[i].y1, y2 = a[i].y2;
int del = a[i].del;
ans += (x - prX) * st.query();
st.update(1, 0, nn - 1, y1, y2 - 1, del);
prX = x;
}
cout << ans << '\n';
return 0;
}
int32_t main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int TET = 1e9;
//cin >> TET;
for (int i = 1; i <= TET; i++)
{
if (solve())
{
break;
}
#ifdef ONPC
cerr << "_____________________________\n";
#endif
}
#ifdef ONPC
cerr << "\nfinished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec\n";
#endif
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3712kb
input:
2 2 2 4 4 3 3 5 5
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
50 0 0 10 3 12 0 22 3 24 0 34 3 36 0 46 3 48 0 58 3 60 0 70 3 72 0 82 3 84 0 94 3 96 0 106 3 108 0 118 3 120 0 130 3 132 0 142 3 144 0 154 3 156 0 166 3 168 0 178 3 180 0 190 3 192 0 202 3 204 0 214 3 216 0 226 3 228 0 238 3 240 0 250 3 252 0 262 3 264 0 274 3 276 0 286 3 288 0 298 3 300 0 310 3 312...
output:
1500
result:
ok single line: '1500'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
50 0 0 30 3 0 5 30 8 0 10 30 13 0 15 30 18 0 20 30 23 0 25 30 28 0 30 30 33 0 35 30 38 0 40 30 43 0 45 30 48 0 50 30 53 0 55 30 58 0 60 30 63 0 65 30 68 0 70 30 73 0 75 30 78 0 80 30 83 0 85 30 88 0 90 30 93 0 95 30 98 0 100 30 103 0 105 30 108 0 110 30 113 0 115 30 118 0 120 30 123 0 125 30 128 0 1...
output:
4500
result:
ok single line: '4500'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
100 0 0 6 6 3 3 9 9 6 6 12 12 9 9 15 15 12 12 18 18 15 15 21 21 18 18 24 24 21 21 27 27 24 24 30 30 27 27 33 33 30 30 36 36 33 33 39 39 36 36 42 42 39 39 45 45 42 42 48 48 45 45 51 51 48 48 54 54 51 51 57 57 54 54 60 60 57 57 63 63 60 60 66 66 63 63 69 69 66 66 72 72 69 69 75 75 72 72 78 78 75 75 81...
output:
2709
result:
ok single line: '2709'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
999 0 0 6 6 3 3 9 9 6 6 12 12 9 9 15 15 12 12 18 18 15 15 21 21 18 18 24 24 21 21 27 27 24 24 30 30 27 27 33 33 30 30 36 36 33 33 39 39 36 36 42 42 39 39 45 45 42 42 48 48 45 45 51 51 48 48 54 54 51 51 57 57 54 54 60 60 57 57 63 63 60 60 66 66 63 63 69 69 66 66 72 72 69 69 75 75 72 72 78 78 75 75 81...
output:
26982
result:
ok single line: '26982'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3712kb
input:
100 0 0 4 2 2 0 6 2 4 0 8 2 6 0 10 2 8 0 12 2 10 0 14 2 12 0 16 2 14 0 18 2 16 0 20 2 18 0 22 2 20 0 24 2 22 0 26 2 24 0 28 2 26 0 30 2 28 0 32 2 30 0 34 2 32 0 36 2 34 0 38 2 36 0 40 2 38 0 42 2 40 0 44 2 42 0 46 2 44 0 48 2 46 0 50 2 48 0 52 2 50 0 54 2 52 0 56 2 54 0 58 2 56 0 60 2 58 0 62 2 60 0...
output:
404
result:
ok single line: '404'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
100 0 0 4 2 0 2 4 4 0 4 4 6 0 6 4 8 0 8 4 10 0 10 4 12 0 12 4 14 0 14 4 16 0 16 4 18 0 18 4 20 0 20 4 22 0 22 4 24 0 24 4 26 0 26 4 28 0 28 4 30 0 30 4 32 0 32 4 34 0 34 4 36 0 36 4 38 0 38 4 40 0 40 4 42 0 42 4 44 0 44 4 46 0 46 4 48 0 48 4 50 0 50 4 52 0 52 4 54 0 54 4 56 0 56 4 58 0 58 4 60 0 60 ...
output:
800
result:
ok single line: '800'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
400 0 0 3000 2 0 4 3000 6 0 8 3000 10 0 12 3000 14 0 16 3000 18 0 20 3000 22 0 24 3000 26 0 28 3000 30 0 32 3000 34 0 36 3000 38 0 40 3000 42 0 44 3000 46 0 48 3000 50 0 52 3000 54 0 56 3000 58 0 60 3000 62 0 64 3000 66 0 68 3000 70 0 72 3000 74 0 76 3000 78 0 80 3000 82 0 84 3000 86 0 88 3000 90 0 ...
output:
2240000
result:
ok single line: '2240000'
Test #9:
score: 0
Accepted
time: 212ms
memory: 49472kb
input:
100000 0 1000000 200000 1000001 1 999999 199999 1000002 2 999998 199998 1000003 3 999997 199997 1000004 4 999996 199996 1000005 5 999995 199995 1000006 6 999994 199994 1000007 7 999993 199993 1000008 8 999992 199992 1000009 9 999991 199991 1000010 10 999990 199990 1000011 11 999989 199989 1000012 12...
output:
20000000000
result:
ok single line: '20000000000'
Test #10:
score: 0
Accepted
time: 130ms
memory: 30508kb
input:
100000 0 0 1000000000 19602 0 20000 1000000000 33235 0 40000 1000000000 56866 0 60000 1000000000 62652 0 80000 1000000000 85686 0 100000 1000000000 119548 0 120000 1000000000 121383 0 140000 1000000000 142985 0 160000 1000000000 166477 0 180000 1000000000 180907 0 200000 1000000000 213625 0 220000 1...
output:
750856076996563747
result:
ok single line: '750856076996563747'
Test #11:
score: 0
Accepted
time: 391ms
memory: 49472kb
input:
100000 804289383 681692777 846930886 714636915 424238335 649760492 957747793 719885386 189641421 25202362 596516649 350490027 102520059 44897763 783368690 967513926 365180540 303455736 540383426 304089172 35005211 294702567 521595368 726956429 336465782 233665123 861021530 278722862 145174067 101513...
output:
999907590278919117
result:
ok single line: '999907590278919117'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3968kb
input:
1000 0 0 1 1000 2 0 3 1000 4 0 5 1000 6 0 7 1000 8 0 9 1000 10 0 11 1000 12 0 13 1000 14 0 15 1000 16 0 17 1000 18 0 19 1000 20 0 21 1000 22 0 23 1000 24 0 25 1000 26 0 27 1000 28 0 29 1000 30 0 31 1000 32 0 33 1000 34 0 35 1000 36 0 37 1000 38 0 39 1000 40 0 41 1000 42 0 43 1000 44 0 45 1000 46 0 4...
output:
750000
result:
ok single line: '750000'