| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 68876 |
2018-08-18T20:53:06 Z |
Crown |
Ideal city (IOI12_city) |
C++14 |
|
406 ms |
32908 KB |
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 1e5+5;
const int md = 1e9;
void add(int &a, int b)
{
a += b;
if(a>= md) a -= md;
}
void sub(int &a, int b)
{
a -= b;
if(a< 0) a += md;
}
int mul(int a, int b)
{
return (1LL*a*b)%md;
}
struct node
{
int x, y1, y2;
vector<int> num, dist;
node(){}
node(int _x, int _y1, int _y2)
{
x = _x; y1 = _y1; y2 = _y2;
}
};
int xmin, ymin;
int xmax, ymax;
vector<int> buck[maxn];
node meg[maxn];
map< ii, int> mp;
vector<int> adj[maxn];
int cnt[maxn];
int findsum(int x)
{
if(x%2 == 0) return mul(x, mul(x/2, x+1));
return mul(x, mul(x, (x+1)/2));
}
int pong = 0;
int lim;
int chote[maxn];
int summ[maxn];
int lalt[maxn];
int ralt[maxn];
int sum(int *ft, int x)
{
x++;
int res = 0;
for(; x; x -= x&(-x)) add(res, ft[x]);
return res;
}
int ask(int *ft, int a, int b)
{
if(a> b) return 0;
int res = sum(ft, b);
sub(res, sum(ft, a-1));
return res;
}
void update(int *ft, int x, int dx)
{
x++;
for(; x<= lim; x += x&(-x)) add(ft[x], dx);
}
void solve(int u, int p)
{
for(auto v : adj[u])
{
if(v == p) continue;
solve(v, u);
}
// printf("HERE %d\n", u);
int len = meg[u].y2-meg[u].y1+1;
meg[u].num.assign(len, 1);
meg[u].dist.assign(len, 0);
vector<int> &num = meg[u].num;
vector<int> &dist = meg[u].dist;
int y1 = meg[u].y1, y2 = meg[u].y2;
lim = len;
int sumdist = 0;
for(int i = 0; i< len; i++)
{
update(summ, i, num[i]);
update(lalt, i, i);
update(ralt, i, len-1-i);
}
for(auto v : adj[u])
{
if(v == p) continue;
// printf("it'ing through %d\n", v);
int yy1 = meg[v].y1, yy2 = meg[v].y2;
vector<int> &nump = meg[v].num;
vector<int> &distp = meg[v].dist;
for(int y = yy1; y<= yy2; y++)
{
int thiscnt = nump[y-yy1];
int thisdist = distp[y-yy1];
add(pong, mul(thiscnt, sumdist));
add(pong, mul(thisdist, ask(summ, 0, len-1)));
if(y1< y && y< y2)
{
int s = y-y1;
add(pong, mul(thiscnt, ask(lalt, s, len-1)));
sub(pong, mul(thiscnt, mul(s-1, ask(summ, s, len-1))));
add(pong, mul(thiscnt, ask(ralt, 0, s-1)));
sub(pong, mul(thiscnt, mul(len-1-s-1, ask(summ, 0, s-1))));
}
else if(y<= y1)
{
add(pong, mul(thiscnt, ask(lalt, 0, len-1)));
add(pong, mul(thiscnt, mul(y1-y+1, ask(summ, 0, len-1))));
}
else
{
add(pong, mul(thiscnt, ask(ralt, 0, len-1)));
add(pong, mul(thiscnt, mul(y-y2+1, ask(summ, 0, len-1))));
}
// printf("pong = %d\n", pong);
}
for(int y = yy1; y<= yy2; y++)
{
int can;
if(y1<= y && y<= y2) can = y;
else if(y< y1) can = y1;
else can = y2;
add(num[can-y1], nump[y-yy1]);
update(summ, can-y1, nump[y-yy1]);
update(lalt, can-y1, mul(can-y1, nump[y-yy1]));
update(ralt, can-y1, mul(len-1-can+y1, nump[y-yy1]));
add(dist[can-y1], distp[y-yy1]); add(sumdist, distp[y-yy1]);
add(dist[can-y1], mul(nump[y-yy1], abs(can-y)+1)); add(sumdist, mul(nump[y-yy1], abs(can-y)+1));
}
// for(int i = 0; i< len; i++) printf("%d ", dist[i]);
// printf("\n");
}
// for(int i = 0; i< len; i++) add(pong, dist[i]);
add(pong, findsum(len));
sub(pong, chote[len]);
for(int i = 1; i<= len; i++) lalt[i] = summ[i] = ralt[i] = 0;
// printf("for %d\n", u);
// printf("dist: ");
// for(int i = 0; i< len; i++) printf("%d ", dist[i]);
// printf("\ncnt: ");
// for(int i = 0; i< len; i++) printf("%d ", num[i]);
// printf("\n");
// printf("pong is %d\n", pong);
// printf("\n\n");
}
int DistanceSum(int N, int *X, int *Y)
{
xmin = ymin = 1e9;
for(int i = 0; i< N; i++) xmin = min(xmin, X[i]), xmax = max(xmax, X[i]);
for(int i = 0; i< N; i++) ymin = min(ymin, Y[i]), ymax = max(ymax, Y[i]);
for(int i = 0; i< N; i++)
{
X[i] -= xmin; Y[i] -= ymin;
buck[X[i]].pb(Y[i]);
}
int n = 0;
for(int i = 0; i< N; i++)
{
sort(buck[i].begin(), buck[i].end());
for(int j = 0; j< (int) buck[i].size(); j++)
{
int y = buck[i][j];
if(j == 0)
{
n++;
meg[n] = node(i, y, y);
}
else if(meg[n].y2+1 != y)
{
n++; meg[n] = node(i, y, y);
}
else
{
meg[n].y2++;
}
mp[ii(i, y)] = n;
}
}
for(int i = 0; i< N; i++)
{
int x = X[i], y = Y[i];
int u = mp[ii(x, y)];
int v1 = mp[ii(x+1, y)];
int v2 = mp[ii(x-1, y)];
if(v1)
{
adj[u].pb(v1); adj[v1].pb(u);
}
if(v2)
{
adj[u].pb(v2); adj[v2].pb(u);
}
}
for(int i = 1; i<= n; i++)
{
sort(adj[i].begin(), adj[i].end());
adj[i].resize(unique(adj[i].begin(), adj[i].end())-adj[i].begin());
}
for(int i = 1; i<= 1e5; i++)
{
add(chote[i], chote[i-1]);
add(chote[i], mul(i, i));
}
solve(1, 0);
return pong;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
11640 KB |
Output is correct |
| 2 |
Correct |
13 ms |
11752 KB |
Output is correct |
| 3 |
Correct |
13 ms |
11828 KB |
Output is correct |
| 4 |
Correct |
15 ms |
11884 KB |
Output is correct |
| 5 |
Correct |
15 ms |
11920 KB |
Output is correct |
| 6 |
Correct |
14 ms |
11920 KB |
Output is correct |
| 7 |
Correct |
15 ms |
11920 KB |
Output is correct |
| 8 |
Correct |
15 ms |
11996 KB |
Output is correct |
| 9 |
Correct |
15 ms |
12044 KB |
Output is correct |
| 10 |
Correct |
15 ms |
12044 KB |
Output is correct |
| 11 |
Correct |
15 ms |
12044 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
12216 KB |
Output is correct |
| 2 |
Correct |
15 ms |
12216 KB |
Output is correct |
| 3 |
Correct |
14 ms |
12268 KB |
Output is correct |
| 4 |
Correct |
17 ms |
12268 KB |
Output is correct |
| 5 |
Correct |
16 ms |
12396 KB |
Output is correct |
| 6 |
Correct |
15 ms |
12396 KB |
Output is correct |
| 7 |
Correct |
17 ms |
12396 KB |
Output is correct |
| 8 |
Correct |
16 ms |
12396 KB |
Output is correct |
| 9 |
Correct |
17 ms |
12396 KB |
Output is correct |
| 10 |
Correct |
14 ms |
12396 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
56 ms |
14312 KB |
Output is correct |
| 2 |
Correct |
53 ms |
14444 KB |
Output is correct |
| 3 |
Correct |
149 ms |
17524 KB |
Output is correct |
| 4 |
Correct |
118 ms |
17524 KB |
Output is correct |
| 5 |
Correct |
286 ms |
23408 KB |
Output is correct |
| 6 |
Correct |
265 ms |
23408 KB |
Output is correct |
| 7 |
Correct |
316 ms |
23408 KB |
Output is correct |
| 8 |
Correct |
300 ms |
23408 KB |
Output is correct |
| 9 |
Correct |
233 ms |
23660 KB |
Output is correct |
| 10 |
Correct |
290 ms |
32908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
32908 KB |
Output is correct |
| 2 |
Correct |
53 ms |
32908 KB |
Output is correct |
| 3 |
Correct |
167 ms |
32908 KB |
Output is correct |
| 4 |
Correct |
174 ms |
32908 KB |
Output is correct |
| 5 |
Correct |
387 ms |
32908 KB |
Output is correct |
| 6 |
Correct |
339 ms |
32908 KB |
Output is correct |
| 7 |
Correct |
406 ms |
32908 KB |
Output is correct |
| 8 |
Correct |
367 ms |
32908 KB |
Output is correct |
| 9 |
Correct |
301 ms |
32908 KB |
Output is correct |
| 10 |
Correct |
340 ms |
32908 KB |
Output is correct |
