| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 124979 |
2019-07-04T09:07:07 Z |
nxteru |
Ideal city (IOI12_city) |
C++14 |
|
21 ms |
10704 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define INF (1LL<<31)-1LL
#define M 1000000000
#define PB push_back
#define F first
#define S second
struct node{
ll s;
map<ll,ll>x;
node(void){
s=0;
x.clear();
}
ll cm(ll l,ll r){
ll res=0;
for(auto i=x.begin();i->F<l&&i!=x.end();i++){
x[i->F+1]+=i->S;
res=(res+i->S)%M;
}
for(auto i=x.end();1;){
i--;
if(i->F<=r||i==x.begin())break;
x[i->F-1]+=i->S;
res=(res+i->S)%M;
}
return res;
}
ll clc(ll l,ll r){
ll res=0,p=0,q=0;
for(auto i=x.begin();i->F<l&&i!=x.end();i++){
p+=i->S;
res=(res+p*(s-p)%M)%M;
}
for(auto i=x.end();1;){
i--;
if(i->F<=r||i==x.begin())break;
q+=i->S;
res=(res+q*(s-p-q)%M)%M;
}
res=(res+p*q%M*(r-l+1LL)%M)%M;
return res;
}
};
struct T{
ll a,b,c;
};
ll n,k,ans;
P q[100005];
node t[100005];
vector<vector<T>>p;
vector<T>g[100005];
void dfs(int v,int par,ll pl,ll pr){
for(int i=0;i<g[v].size();i++){
ll u=g[v][i].a,l=g[v][i].b,r=g[v][i].c;
if(u==par)continue;
dfs(u,v,l,r);
ans=(ans+(n-t[u].s)*(t[u].cm(l,r)+t[u].s)%M)%M;
for(int j=l;j<=r;j++)t[v].x[j]+=t[u].x[j];
t[v].s+=t[u].s;
}
ans=(ans+t[v].clc(pl,pr))%M;
}
int DistanceSum(int N, int *X, int *Y) {
n=N;
for(int i=0;i<n;i++)q[i]=P(Y[i],X[i]);
sort(q,q+n);
vector<T>o;
o.clear();
for(int i=0;i<n;i++){
if(i==0||q[i-1].F!=q[i].F)p.PB(o);
if(p.back().size()==0||p.back().back().b!=q[i].S-1)p.back().PB(T{q[i].S,q[i].S,k++});
else p.back().back().b++;
}
for(int i=0;i<p.size();i++){
int w=0;
for(int j=0;j<p[i].size();j++){
ll v=p[i][j].c,a=p[i][j].a,b=p[i][j].b;
t[v].s=b-a+1LL;
for(int z=a;z<=b;z++)t[v].x[z]++;
while(i>0&&w<p[i-1].size()&&p[i-1][w].b<a)w++;
while(i>0&&w<p[i-1].size()&&p[i-1][w].a<=b){
ll u=p[i-1][w].c,l=max(p[i-1][w].a,a),r=min(p[i-1][w].b,b);
g[v].PB(T{u,l,r});
g[u].PB(T{v,l,r});
w++;
}
}
}
dfs(0,-1,INF,INF);
return ans;
}
Compilation message
city.cpp: In function 'void dfs(int, int, ll, ll)':
city.cpp:56:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[v].size();i++){
~^~~~~~~~~~~~
city.cpp: In function 'int DistanceSum(int, int*, int*)':
city.cpp:77:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<p.size();i++){
~^~~~~~~~~
city.cpp:79:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j=0;j<p[i].size();j++){
~^~~~~~~~~~~~
city.cpp:83:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i>0&&w<p[i-1].size()&&p[i-1][w].b<a)w++;
~^~~~~~~~~~~~~~
city.cpp:84:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i>0&&w<p[i-1].size()&&p[i-1][w].a<=b){
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
8184 KB |
Output is correct |
| 2 |
Incorrect |
9 ms |
8184 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
8312 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
9976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
21 ms |
10704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
