oj.uz

Submission #93799

# Submission time Handle Problem Language Result Execution time Memory
93799 2019-01-11T12:25:30 Z pranjalssh Ideal city (IOI12_city) C++14
100 / 100
 133 ms 22744 KB 
#include <bits/stdc++.h>
using namespace std;

#define cerr cout
#define F first
#define S second
#define FOR(i,a,b) for (auto i = (a); i <= (b); ++i)
#define NFOR(i,a,b) for(auto i = (a); i >= (b); --i)
#define all(x) (x).begin(), (x).end()
#define sz(x) int(x.size())
typedef long long ll; typedef pair <int, int> ii; typedef vector <int> vi; const ll inf = 2e9;
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)


ii intersect(ii a, ii b) {
	return ii(max(a.F, b.F), min(a.S, b.S));
}

#define get(x,y) (lower_bound(all(a),ii(x,y))-a.begin())

int DistanceSum(int N, int *X, int *Y) {
	int n = N;
	vector<ii> a(n);
	FOR (i, 0, n - 1) {
		a[i] = ii(X[i], Y[i]);
	}
	sort(all(a));
	map<ii, int> no;
	vector<ii> sg;
	vector<vi> t(n);
	
	FOR (i, 0, n - 1) {
		int x = a[i].F, y = a[i].S;
		int j = i;
		while (j+1 < n and a[j+1].F == x and a[j+1].S == a[j].S+1) ++j;
		FOR (it, i, j) no[a[it]] = sz(sg);
		FOR (it, i, j) {
			ii cur(a[it].F-1,a[it].S);
			if (no.count(cur)) {
				t[sz(sg)].emplace_back(no[cur]);
				t[no[cur]].emplace_back(sz(sg));
			}
		}
		sg.emplace_back(i, j);
		i = j;
	}
	FOR (i, 0, n - 1) {
		sort(all(t[i])); t[i].erase(unique(all(t[i])), t[i].end());
	}
	// pr(t);
	ll ans = 0;
	vector<ll> down(n), up(n), same(n);
	vector<ll> downC(n), upC(n), sameC(n);
	function<void(int,int)> dfsD = [&](int u, int par) {

		for (int v: t[u]) if (v != par) dfsD(v, u);

		int i = sg[u].F, j = sg[u].S;
		int x = a[i].F, y1 = a[i].S, y2 = a[j].S;

		int l = 0, r = j-i;
		// pr(t);
		FOR (it, i, j) {
			int y = a[it].S;
			sameC[it] = l + r + 1;
			same[it] = (r*(r+1LL)/2 + l*(l+1LL)/2) % inf;
			++l, --r;
			for (int v: t[u]) if (v != par) {
				ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));

				int ptr = -1;
				if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
				else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
				else ptr = get(a[sg[v].F].F, pt.S);

				ll d = 1 + abs(y - a[ptr].S);
				// pr(a[it],a[ptr]);
				// pr(a[it],v,d);
				downC[it] += downC[ptr] + sameC[ptr];
				down[it] = (down[it] + d * downC[ptr] + down[ptr]) % inf;
				down[it] = (down[it] + d * sameC[ptr] + same[ptr]) % inf;
			}
			// pr(a[it], down[it]);
		}
		
	};


	function<void(int,int)> dfsU = [&](int u, int par) {

		int i = sg[u].F, j = sg[u].S;
		int x = a[i].F, y1 = a[i].S, y2 = a[j].S;

		FOR (it, i, j) if (par>=0) {
			int y = a[it].S;
			
			int v = par;
			ii pt = intersect(ii(y1, y2), ii(a[sg[v].F].S, a[sg[v].S].S));

			int ptr = -1;
			if (y >= pt.F and y <= pt.S) ptr = get(a[sg[v].F].F, y);
			else if (abs(y-pt.F) < abs(y-pt.S)) ptr = get(a[sg[v].F].F, pt.F);
			else ptr = get(a[sg[v].F].F, pt.S);

			ll d = 1 + abs(y - a[ptr].S);
			upC[it] += upC[ptr] + sameC[ptr];
			upC[it] += downC[ptr] - downC[it] - sameC[it];

			up[it] = (up[it] + d*upC[ptr] + up[ptr] + same[ptr] + d*sameC[ptr]) % inf;
			up[it] = (up[it] + d*downC[ptr] + down[ptr]) % inf;
			int o = get(x,a[ptr].S);
			// pr(a[it], par, a[ptr], a[o]);
			up[it] = (up[it] - (d+1)*downC[o] - down[o])%inf;
			up[it] = (up[it] - (d+1)*sameC[o] - same[o])%inf;
			if (up[it] < 0) up[it] += inf;
			// pr(a[it], a[ptr], upC[it]);
		}

		for (int v: t[u]) if (v != par) dfsU(v, u);
		
	};


	dfsD(0, -1);
	dfsU(0, -1);

	FOR (i, 0, n - 1) ans = (ans + up[i] + down[i] + same[i]) % inf;
	
	return ans/2;
}

// int main() {
// 	int n; cin >> n;
// 	vi x(n), y(n);
// 	FOR (i, 0, n - 1)cin >> x[i] >> y[i];
// 	cout << DistanceSum(n, &x[0], &y[0]) << "\n";
// }

Compilation message

city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:42:19: warning: unused variable 'y' [-Wunused-variable]
   int x = a[i].F, y = a[i].S;
                   ^
city.cpp: In lambda function:
city.cpp:68:7: warning: unused variable 'x' [-Wunused-variable]
   int x = a[i].F, y1 = a[i].S, y2 = a[j].S;
       ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 552 KB Output is correct
5 Correct 4 ms 760 KB Output is correct
6 Correct 4 ms 632 KB Output is correct
7 Correct 4 ms 760 KB Output is correct
8 Correct 4 ms 632 KB Output is correct
9 Correct 4 ms 632 KB Output is correct
10 Correct 4 ms 632 KB Output is correct

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 3832 KB Output is correct
2 Correct 20 ms 3960 KB Output is correct
3 Correct 50 ms 8892 KB Output is correct
4 Correct 48 ms 8952 KB Output is correct
5 Correct 96 ms 17400 KB Output is correct
6 Correct 102 ms 17528 KB Output is correct
7 Correct 106 ms 17656 KB Output is correct
8 Correct 101 ms 17288 KB Output is correct
9 Correct 101 ms 17400 KB Output is correct
10 Correct 114 ms 22744 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 3960 KB Output is correct
2 Correct 22 ms 4216 KB Output is correct
3 Correct 57 ms 9204 KB Output is correct
4 Correct 56 ms 9336 KB Output is correct
5 Correct 122 ms 18032 KB Output is correct
6 Correct 115 ms 17784 KB Output is correct
7 Correct 133 ms 18288 KB Output is correct
8 Correct 129 ms 17916 KB Output is correct
9 Correct 121 ms 17440 KB Output is correct
10 Correct 109 ms 17484 KB Output is correct