Submission #66184899

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
#define fep(i, s, e) for(int (i) = (s); (i) < (e); ++ i)
#define _rep(i, s, e) for(int (i) = (s); (i) >= (e); -- i)
#define _fep(i, s, e) for(int (i) = (s); (i) > (e); -- i)

#define int long long
#define pii pair<int, int>

using namespace std;

const int inf = numeric_limits<int>::max();
const int ninf = numeric_limits<int>::min();
const int mod = inf;

int n, l[300005], r[300005], tmp[300005], to[600005], cntst[600005], cnted[600005], cnt, ans, prvans, sufans, ql, qr;
struct node {
	node() {
		return;
	}
	node(int _x, int _id, int _st) {
		x = _x, id = _id, st = _st;
		return;
	}
	int x, id, st;
} a[600005];

void solve() {
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld %lld", &l[0], &r[0]), a[i] = node(l[0], i, 1), a[i + n] = node(r[0], i, 2);
	sort(a + 1, a + 1 + 2 * n, [](node a, node b) {
		return a.x < b.x;
	});
	rep(i, 1, 2 * n) {
		if(a[i].x != a[i - 1].x) ++cnt, to[cnt] = a[i].x;
		if(a[i].st == 1) l[a[i].id] = cnt;
		else r[a[i].id] = cnt;
	}
	rep(i, 1, n) tmp[i] = l[i], ++cntst[l[i]], ++cnted[r[i]];
	sort(tmp + 1, tmp + 1 + n);
	fep(i, 1, n) sufans += (to[tmp[i + 1]] - to[tmp[i]]) * i * (n - i);
	ans = sufans;
	rep(i, 1, cnt) {
		if(cnted[i - 1]) prvans += (to[i - 1] - to[tmp[ql]]) * ql * (n - ql);
		while(cnted[i - 1]--) tmp[++ql] = i - 1;
		qr += cntst[i];
		if(cntst[i]) sufans -= (to[tmp[qr + 1]] - to[i]) * (qr) * (n - qr);
		ans = min(ans, prvans + sufans + ((to[i] - to[tmp[ql]]) * ql * (n - ql)) + ((to[tmp[qr + 1]] - to[i]) * qr * (n - qr)));
	}
	printf("%lld\n", ans);
	return;
}

signed main() {
	int T = 1;
	while(T--) solve();
	return 0;
}

Submission Info

Submission Time
Task C - Min Diff Sum
User Getaway_Car
Language C++ 17 (gcc 12.2)
Score 600
Code Size 1726 Byte
Status AC
Exec Time 127 ms
Memory 36556 KiB

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:31:9: note: in expansion of macro ‘rep’
   31 |         rep(i, 1, n) scanf("%lld %lld", &l[0], &r[0]), a[i] = node(l[0], i, 1), a[i + n] = node(r[0], i, 2);
      |         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:31:9: note: in expansion of macro ‘rep’
   31 |         rep(i, 1, n) scanf("%lld %lld", &l[0], &r[0]), a[i] = node(l[0], i, 1), a[i + n] = node(r[0], i, 2);
      |         ^~~
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:35:9: note: in expansion of macro ‘rep’
   35 |         rep(i, 1, 2 * n) {
      |         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:35:9: note: in expansion of macro ‘rep’
   35 |         rep(i, 1, 2 * n) {
      |         ^~~
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:40:9: note: in expansion of macro ‘rep’
   40 |         rep(i, 1, n) tmp[i] = l[i], ++cntst[l[i]], ++cnted[r[i]];
      |         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:40:9: note: in expansion of macro ‘rep’
   40 |         rep(i, 1, n) tmp[i] = l[i], ++cntst[l[i]], ++cnted[r[i]];
      |         ^~~
Main.cpp:4:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    4 | #define fep(i, s, e) for(int (i) = (s); (i) < (e); ++ i)
      |                              ^~~
Main.cpp:42:9: note: in expansion of macro ‘fep’
   42 |         fep(i, 1, n) sufans += (to[tmp[i + 1]] - to[tmp[i]]) * i * (n - i);
      |         ^~~
Main.cpp:4:30: note: remove parentheses
    4 | #define fep(i, s, e) for(int (i) = (s); (i) < (e); ++ i)
      |                              ^~~
Main.cpp:42:9: note: in expansion of macro ‘fep’
   42 |         fep(i, 1, n) sufans += (to[tmp[i + 1]] - to[tmp[i]]) * i * (n - i);
      |         ^~~
Main.cpp:3:30: warning: unnecessary parentheses in declaration of ‘i’ [-Wparentheses]
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:44:9: note: in expansion of macro ‘rep’
   44 |         rep(i, 1, cnt) {
      |         ^~~
Main.cpp:3:30: note: remove parentheses
    3 | #define rep(i, s, e) for(int (i) = (s); (i) <= (e); ++ i)
      |                              ^~~
Main.cpp:44:9: note: in expansion of macro ‘rep’
   44 |         rep(i, 1, cnt) {
      |         ^~~
Main.cpp:30:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   30 |         scanf("%lld", &n);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:31:27: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   31 |         rep(i, 1, n) scanf("%lld %lld", &l[0], &r[0]), a[i] = node(l[0], i, 1), a[i + n] = node(r[0], i, 2);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 56
Set Name Test Cases
Sample sample_00.txt, sample_01.txt, sample_02.txt
All case_00.txt, case_01.txt, case_02.txt, case_03.txt, case_04.txt, case_05.txt, case_06.txt, case_07.txt, case_08.txt, case_09.txt, case_10.txt, case_11.txt, case_12.txt, case_13.txt, case_14.txt, case_15.txt, case_16.txt, case_17.txt, case_18.txt, case_19.txt, case_20.txt, case_21.txt, case_22.txt, case_23.txt, case_24.txt, case_25.txt, case_26.txt, case_27.txt, case_28.txt, case_29.txt, case_30.txt, case_31.txt, case_32.txt, case_33.txt, case_34.txt, case_35.txt, case_36.txt, case_37.txt, case_38.txt, case_39.txt, case_40.txt, case_41.txt, case_42.txt, case_43.txt, case_44.txt, case_45.txt, case_46.txt, case_47.txt, case_48.txt, case_49.txt, case_50.txt, case_51.txt, case_52.txt, sample_00.txt, sample_01.txt, sample_02.txt
Case Name Status Exec Time Memory
case_00.txt AC 1 ms 3932 KiB
case_01.txt AC 1 ms 3796 KiB
case_02.txt AC 1 ms 3868 KiB
case_03.txt AC 1 ms 3740 KiB
case_04.txt AC 1 ms 3808 KiB
case_05.txt AC 118 ms 35264 KiB
case_06.txt AC 45 ms 16196 KiB
case_07.txt AC 74 ms 24000 KiB
case_08.txt AC 75 ms 24316 KiB
case_09.txt AC 23 ms 10172 KiB
case_10.txt AC 47 ms 16960 KiB
case_11.txt AC 3 ms 4160 KiB
case_12.txt AC 86 ms 27104 KiB
case_13.txt AC 76 ms 24728 KiB
case_14.txt AC 95 ms 29484 KiB
case_15.txt AC 46 ms 16376 KiB
case_16.txt AC 88 ms 27560 KiB
case_17.txt AC 109 ms 32852 KiB
case_18.txt AC 55 ms 18912 KiB
case_19.txt AC 77 ms 25060 KiB
case_20.txt AC 78 ms 24852 KiB
case_21.txt AC 66 ms 21960 KiB
case_22.txt AC 118 ms 35468 KiB
case_23.txt AC 24 ms 10628 KiB
case_24.txt AC 23 ms 9920 KiB
case_25.txt AC 32 ms 12780 KiB
case_26.txt AC 101 ms 31192 KiB
case_27.txt AC 97 ms 30372 KiB
case_28.txt AC 74 ms 24068 KiB
case_29.txt AC 123 ms 36556 KiB
case_30.txt AC 94 ms 29388 KiB
case_31.txt AC 114 ms 34532 KiB
case_32.txt AC 11 ms 7076 KiB
case_33.txt AC 113 ms 34432 KiB
case_34.txt AC 118 ms 35600 KiB
case_35.txt AC 38 ms 17712 KiB
case_36.txt AC 21 ms 11588 KiB
case_37.txt AC 5 ms 5168 KiB
case_38.txt AC 12 ms 8144 KiB
case_39.txt AC 18 ms 10348 KiB
case_40.txt AC 2 ms 4264 KiB
case_41.txt AC 53 ms 23332 KiB
case_42.txt AC 25 ms 13184 KiB
case_43.txt AC 11 ms 7716 KiB
case_44.txt AC 17 ms 9800 KiB
case_45.txt AC 126 ms 36192 KiB
case_46.txt AC 126 ms 36236 KiB
case_47.txt AC 127 ms 36384 KiB
case_48.txt AC 101 ms 31848 KiB
case_49.txt AC 127 ms 36324 KiB
case_50.txt AC 126 ms 36316 KiB
case_51.txt AC 127 ms 36264 KiB
case_52.txt AC 101 ms 31920 KiB
sample_00.txt AC 1 ms 3792 KiB
sample_01.txt AC 1 ms 3804 KiB
sample_02.txt AC 1 ms 3736 KiB