QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#856219#3938. Gameworld TornadoWeaRD276AC ✓391ms49472kbC++202.6kb2025-01-13 19:03:062025-01-13 19:03:06

Judging History

This is the latest submission verdict.

  • [2025-01-13 19:03:06]
  • Judged
  • Verdict: AC
  • Time: 391ms
  • Memory: 49472kb
  • [2025-01-13 19:03:06]
  • Submitted

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'