QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#574438 | #3938. Gameworld Tornado | LaVuna47 | AC ✓ | 219ms | 33828kb | C++17 | 10.6kb | 2024-09-18 22:07:05 | 2024-09-18 22:07:08 |
Judging History
answer
/** gnu specific **/
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
/** contains everything I need in std **/
#include <bits/stdc++.h>
#ifndef ATCODER_LAZYSEGTREE_HPP
#define ATCODER_LAZYSEGTREE_HPP 1
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifndef ATCODER_INTERNAL_BITOP_HPP
#define ATCODER_INTERNAL_BITOP_HPP 1
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
#endif // ATCODER_INTERNAL_BITOP_HPP
namespace atcoder {
#if __cplusplus >= 201703L
template <class S,
auto op,
auto e,
class F,
auto mapping,
auto composition,
auto id>
struct lazy_segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
static_assert(
std::is_convertible_v<decltype(mapping), std::function<S(F, S)>>,
"mapping must work as S(F, S)");
static_assert(
std::is_convertible_v<decltype(composition), std::function<F(F, F)>>,
"composition must work as F(F, F)");
static_assert(std::is_convertible_v<decltype(id), std::function<F()>>,
"id must work as F()");
#else
template <class S,
S (*op)(S, S),
S (*e)(),
class F,
S (*mapping)(F, S),
F (*composition)(F, F),
F (*id)()>
struct lazy_segtree {
#endif
public:
lazy_segtree() : lazy_segtree(0) {}
explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
explicit lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
lz = std::vector<F>(size, id());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
return d[p];
}
S prod(int l, int r) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return e();
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
S sml = e(), smr = e();
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() { return d[1]; }
void apply(int p, F f) {
assert(0 <= p && p < _n);
p += size;
for (int i = log; i >= 1; i--) push(p >> i);
d[p] = mapping(f, d[p]);
for (int i = 1; i <= log; i++) update(p >> i);
}
void apply(int l, int r, F f) {
assert(0 <= l && l <= r && r <= _n);
if (l == r) return;
l += size;
r += size;
for (int i = log; i >= 1; i--) {
if (((l >> i) << i) != l) push(l >> i);
if (((r >> i) << i) != r) push((r - 1) >> i);
}
{
int l2 = l, r2 = r;
while (l < r) {
if (l & 1) all_apply(l++, f);
if (r & 1) all_apply(--r, f);
l >>= 1;
r >>= 1;
}
l = l2;
r = r2;
}
for (int i = 1; i <= log; i++) {
if (((l >> i) << i) != l) update(l >> i);
if (((r >> i) << i) != r) update((r - 1) >> i);
}
}
template <bool (*g)(S)> int max_right(int l) {
return max_right(l, [](S x) { return g(x); });
}
template <class G> int max_right(int l, G g) {
assert(0 <= l && l <= _n);
assert(g(e()));
if (l == _n) return _n;
l += size;
for (int i = log; i >= 1; i--) push(l >> i);
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!g(op(sm, d[l]))) {
while (l < size) {
push(l);
l = (2 * l);
if (g(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*g)(S)> int min_left(int r) {
return min_left(r, [](S x) { return g(x); });
}
template <class G> int min_left(int r, G g) {
assert(0 <= r && r <= _n);
assert(g(e()));
if (r == 0) return 0;
r += size;
for (int i = log; i >= 1; i--) push((r - 1) >> i);
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!g(op(d[r], sm))) {
while (r < size) {
push(r);
r = (2 * r + 1);
if (g(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
std::vector<F> lz;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
void all_apply(int k, F f) {
d[k] = mapping(f, d[k]);
if (k < size) lz[k] = composition(f, lz[k]);
}
void push(int k) {
all_apply(2 * k, lz[k]);
all_apply(2 * k + 1, lz[k]);
lz[k] = id();
}
};
} // namespace atcoder
#endif // ATCODER_LAZYSEGTREE_HPP
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(S) ((int)S.size())
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define RFOR(i, n) for(int i = n-1; i >= 0; --i)
#define output_vec(vec) { FOR(i_, sz(vec)) cout << vec[i_] << ' '; cout << '\n'; }
#define x first
#define y second
#define pb push_back
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef vector<bool> vb;
typedef short si;
typedef unsigned long long ull;
typedef long double LD;
typedef pair<ull, ull> pull;
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
using namespace std;
#ifdef ONPC
mt19937 rnd(228);
#else
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
// addition on interval / min operation
struct S
{
ll min_val;
ll sum_val;
};
using F = ll;
const ll INF = 1e18;
S op(S a, S b)
{
if(a.min_val < b.min_val)
return a;
else if(a.min_val > b.min_val)
return b;
else
return {a.min_val, a.sum_val + b.sum_val};
}
S e()
{
return {INF, 0ll};
}
// f(g(x))
S mapping(F f, S x)
{
return {f+x.min_val, x.sum_val};
}
F composition(F f, F g)
{
return f+g;
}
F id(){ return 0ll; }
struct Rectangle
{
pll p1, p2;
};
struct Event
{
ll x;
bool begin;
int rect_id;
};
int solve()
{
int n;
if(!(cin >> n))
return 1;
vector<Rectangle> a(n);
FOR(i, n) cin >> a[i].p1.x >> a[i].p1.y >> a[i].p2.x >> a[i].p2.y;
vector<ll> arr;
{ // linear mapping
set<ll> ss;
FOR(i, n) ss.insert(a[i].p1.y), ss.insert(a[i].p2.y);
unordered_map<ll, ll> I;
int ctr = 0;
for(auto item: ss)
I[item] = ctr++;
vector<ll> vec{all(ss)};
FOR(i, sz(vec)-1)
{
arr.pb(vec[i+1]-vec[i]);
}
FOR(i, n) a[i].p1.y = I[a[i].p1.y], a[i].p2.y = I[a[i].p2.y];
}
ll sum_arr = accumulate(all(arr), 0ll);
// preparing events
vector<Event> events;
FOR(i, n)
{
events.pb(Event{a[i].p1.x, true, i});
events.pb(Event{a[i].p2.x, false, i});
}
sort(all(events), [](const Event& e1, const Event& e2) -> bool {
if(e1.x == e2.x)
{
return (int)e1.begin < (int)e2.begin;
}
return e1.x < e2.x;
});
// preparing segment tree
int N = sz(arr);
std::vector<S> v(N+10, {0, 0});
FOR(i, N) v[i] = {0, arr[i]};
atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(v);
ll pr_x = events[0].x;
ll res = 0;
for(auto [x, begin, rect_id]: events)
{
ll dx = x-pr_x;
res += dx * (sum_arr-seg.all_prod().sum_val);
if(begin)
{
seg.apply(a[rect_id].p1.y, a[rect_id].p2.y, 1);
}
else
{
seg.apply(a[rect_id].p1.y, a[rect_id].p2.y, -1);
}
pr_x = x;
}
cout << res << '\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
cout << "__________________________" << endl;
#endif
}
#ifdef ONPC
cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
#endif
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3644kb
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: 3644kb
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: 3820kb
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: 3900kb
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: 1ms
memory: 4020kb
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: 3720kb
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: 0ms
memory: 3612kb
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: 1ms
memory: 3924kb
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: 144ms
memory: 33828kb
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: 97ms
memory: 20160kb
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: 219ms
memory: 33708kb
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: 1ms
memory: 4064kb
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'