| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 68847 |
2018-08-18T19:06:59 Z |
Crown |
Ideal city (IOI12_city) |
C++14 |
|
81 ms |
18812 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;
}
int mul(int a, int b)
{
return (1LL*a*b)%md;
}
struct node
{
int x, y1, y2;
vector<int> res, 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 dim;
int stL[4*maxn];
int stR[4*maxn];
int lzL[4*maxn];
int lzR[4*maxn];
void build(int *st, int *lz, int p = 1, int L = 0, int R = dim-1)
{
st[p] = 0; lz[p] = 0;
if(L == R)
{
return;
}
build(st, lz, 2*p, L, (L+R)/2);
build(st, lz, 2*p+1, (L+R)/2+1, R);
}
int ask(int *st, int *lz, int i, int j, int p = 1, int L = 0, int R = dim-1)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j) return st[p];
int M = (L+R)/2;
if(lz[p])
{
add(st[2*p], mul(M-L+1, lz[p]));
add(st[2*p+1], mul(R-M, lz[p]));
add(lz[2*p], lz[p]);
add(lz[2*p+1], lz[p]);
lz[p] = 0;
}
int x = ask(st, lz, i, j, 2*p, L, (L+R)/2);
int y = ask(st, lz, i, j, 2*p+1, (L+R)/2+1, R);
add(x, y);
return x;
}
void update(int *st, int *lz, int i, int j, int dx, int p = 1, int L = 0, int R = dim-1)
{
if(i> R || j< L) return;
if(i<= L && R<= j)
{
// printf("updated at %d (%d %d)\n", p, L, R);
add(st[p], mul(R-L+1, dx));
add(lz[p], dx);
return;
}
int M = (L+R)/2;
if(lz[p])
{
add(st[2*p], mul(M-L+1, lz[p]));
add(st[2*p+1], mul(R-M, lz[p]));
add(lz[2*p], lz[p]);
add(lz[2*p+1], lz[p]);
lz[p] = 0;
}
update(st, lz, i, j, dx, 2*p, L, (L+R)/2); update(st, lz, i, j, dx, 2*p+1, (L+R)/2+1, R);
st[p] = st[2*p];
add(st[p], st[2*p+1]);
}
int findsum(int x)
{
if(x%2 == 0) return mul(x/2, x+1);
return mul(x, (x+1)/2);
}
int pong = 0;
void solve(int u, int p)
{
for(auto v : adj[u])
{
if(v == p) continue;
solve(v, u);
}
int len = meg[u].y2-meg[u].y1+1;
cnt[u] = len;
meg[u].res.assign(len, 0);
meg[u].num.assign(len, 1);
meg[u].dist.assign(len, 0);
dim = len; build(stL, lzL); build(stR, lzR);
for(int i = 0; i< len; i++)
{
meg[u].res[i] = findsum(i);
add(meg[u].res[i], findsum(len-1-i));
}
// printf("now %d\n", u);
for(auto v : adj[u])
{
if(v == p) continue;
printf("it'ing over %d\n", v);
for(int y = meg[v].y1; y<= meg[v].y2; y++)
{
int cnt = meg[v].num[y-meg[v].y1];
int dist = meg[v].dist[y-meg[v].y1];
int can;
if(meg[u].y1<= y && y<= meg[u].y2)
{
can = y;
add(dist, cnt);
}
else if(y< meg[u].y1)
{
can = meg[u].y1;
add(dist, mul(meg[u].y1-y+1, cnt));
}
else
{
can = meg[u].y2;
add(dist, mul(y-meg[u].y2+1, cnt));
}
printf("added %d*%d\n", dist, meg[u].res[can-meg[u].y1]+ask(stL, lzL, 0, can-meg[u].y1)+ask(stR, lzR, can-meg[u].y1, meg[u].y2-meg[u].y1));
add(pong, mul(dist, meg[u].res[can-meg[u].y1]));
add(pong, mul(dist, ask(stL, lzL, 0, can-meg[u].y1)));
add(pong, mul(dist, ask(stR, lzR, can-meg[u].y1, meg[u].y2-meg[u].y1)));
}
for(int y = meg[v].y1; y<= meg[v].y2; y++)
{
if(meg[u].y1<= y && y<= meg[u].y2)
{
add(meg[u].res[y-meg[u].y1], meg[v].res[y-meg[v].y1]);
add(meg[u].res[y-meg[u].y1], cnt[v]);
}
}
int temp = meg[v].res.back(); add(temp, 2*cnt[v]);
update(stL, lzL, meg[v].y2+1-meg[u].y1, meg[v].y2+1-meg[u].y1, temp);
// printf("temp is %d at %d\n", temp, meg[v].y2+1-meg[u].y1);
update(stL, lzL, meg[v].y2+2-meg[u].y1, dim-1, cnt[v]);
temp = meg[v].res[0]; add(temp, 2*cnt[v]);
update(stR, lzR, meg[v].y1-1-meg[u].y1, meg[v].y1-1-meg[u].y1, temp);
update(stR, lzR, 0, meg[v].y1-2-meg[u].y1, cnt[v]);
cnt[u] += cnt[v];
for(int y = meg[v].y1; y<= meg[v].y2; y++)
{
if(meg[u].y1<= y && y<= meg[u].y2)
{
add(meg[u].num[y-meg[u].y1], meg[v].num[y-meg[v].y1]);
add(meg[u].dist[y-meg[u].y1], meg[v].dist[y-meg[v].y1]);
add(meg[u].dist[y-meg[u].y1], meg[v].num[y-meg[v].y1]);
}
else if(y< meg[u].y1)
{
add(meg[u].num[0], meg[v].num[y-meg[v].y1]);
add(meg[u].dist[0], meg[v].dist[y-meg[v].y1]);
add(meg[u].dist[0], mul(meg[u].y1-y+1, meg[v].num[y-meg[v].y1]));
}
else
{
add(meg[u].num.back(), meg[v].num[y-meg[v].y1]);
add(meg[u].dist.back(), meg[v].dist[y-meg[v].y1]);
add(meg[u].dist.back(), mul(y-meg[u].y2+1, meg[v].num[y-meg[v].y1]));
}
}
printf("res: ");
for(int i = 0; i< len; i++) printf("%d ", meg[u].res[i]+ask(stL, lzL, 0, i)+ask(stR, lzR, i, dim-1));
printf("\n");
}
for(int i = 0; i< len; i++)
{
add(meg[u].res[i], ask(stL, lzL, 0, i));
add(meg[u].res[i], ask(stR, lzR, i, dim-1));
}
printf("meg[%d]:\n", u);
printf("res: ");
for(int i = 0; i< len; i++) printf("%d ", meg[u].res[i]);
printf("\n");
printf("dist: ");
for(int i = 0; i< len; i++) printf("%d ", meg[u].dist[i]);
printf("\n");
printf("num: ");
for(int i = 0; i< len; i++) printf("%d ", meg[u].num[i]);
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());
}
solve(1, 0);
return pong;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
13688 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
17 ms |
13936 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
17080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
81 ms |
18812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
