Submission #576685

#TimeUsernameProblemLanguageResultExecution timeMemory
576685benson1029Ideal city (IOI12_city)C++14
100 / 100
71 ms39400 KiB
#include<bits/stdc++.h> using namespace std; long long mod = 1e9; vector<int> XX, YY; int n; vector<int> y[200005]; long long ans = 0; vector< pair<long long,long long> > y_lst[200005]; long long calcarr(vector<long long> x, vector<long long> y) { long long rv = 0, sum1 = 0, sum2 = 0; for(int i=0; i<x.size(); i++) { rv += x[i] * y[i]; sum1 += x[i]; sum2 += y[i]; } sum1 %= mod; sum2 %= mod; rv %= mod; return (sum1*sum2-rv) % mod; } long long calcarr2(vector<long long> x, vector<long long> y) { long long rv = 0; long long prevcount = 0, prevsum = 0; for(int i=0; i<x.size(); i++) { rv += ((prevcount * i - prevsum) % mod) * x[i]; rv %= mod; prevcount += x[i]; prevsum += i * x[i]; prevsum %= mod; } return rv; } pair< vector<long long>, vector<long long> > dfs(int x, int y, int px, int py) { vector<long long> rv, rvdis; long long tmpans = 0; rv.resize(y_lst[x][y].second - y_lst[x][y].first + 1); rvdis.resize(rv.size()); for(int i=0; i<rv.size(); i++) rv[i] = 1; for(int i=0; i<rv.size(); i++) rvdis[i] = 0; auto process = [] (int nx, int x, int y, int px, int py, vector<long long> &rv, vector<long long> &rvdis, long long &tmpans) { int l = upper_bound(y_lst[nx].begin(), y_lst[nx].end(), make_pair(y_lst[x][y].first, y_lst[x][y].first)) - y_lst[nx].begin() - 1; if(l < 0) l = 0; int r = lower_bound(y_lst[nx].begin(), y_lst[nx].end(), make_pair(y_lst[x][y].second, y_lst[x][y].second)) - y_lst[nx].begin(); if(r >= y_lst[nx].size()) r = y_lst[nx].size() - 1; for(int i=l; i<=r; i++) { if(!(y_lst[nx][i].first > y_lst[x][y].second || y_lst[nx][i].second < y_lst[x][y].first)) { if(!(px==nx && py==i)) { auto ttmp = dfs(nx, i, x, y); auto tmp = ttmp.first; auto tmpdis = ttmp.second; //tmpans -= calcarr(tmp, tmpdis); //tmpans %= mod; for(int j=0; j<tmp.size(); j++) { int AY = y_lst[nx][i].first + j; int BY = AY; if(BY > y_lst[x][y].second) BY = y_lst[x][y].second; if(BY < y_lst[x][y].first) BY = y_lst[x][y].first; tmpans += rvdis[BY - y_lst[x][y].first] * tmp[j] + rv[BY - y_lst[x][y].first] * (tmpdis[j] + tmp[j] * (1+abs(BY-AY))); tmpans %= mod; } int BYprev = -1; vector<long long> tmprv, tmprvdis; tmprv.clear(); tmprvdis.clear(); for(int j=0; j<tmp.size(); j++) { int AY = y_lst[nx][i].first + j; int BY = AY; if(BY > y_lst[x][y].second) BY = y_lst[x][y].second; if(BY < y_lst[x][y].first) BY = y_lst[x][y].first; rv[BY - y_lst[x][y].first] += tmp[j]; rvdis[BY - y_lst[x][y].first] += tmpdis[j] + tmp[j] * (1+abs(BY-AY)); if(BYprev==-1 || BY!=BYprev) { BYprev = BY; tmprv.push_back(tmp[j]); tmprvdis.push_back(tmpdis[j] + tmp[j] * (1+abs(BY-AY))); } else { tmprv[tmprv.size()-1] += tmp[j]; tmprvdis[tmprvdis.size()-1] += tmpdis[j] + tmp[j] * (1+abs(BY-AY)); } } tmpans -= calcarr(tmprv, tmprvdis); tmpans -= calcarr2(tmprv, tmprvdis); tmpans %= mod; } } } }; if(x>0) process(x-1, x, y, px, py, rv, rvdis, tmpans); process(x+1, x, y, px, py, rv, rvdis, tmpans); tmpans += calcarr(rv, rvdis); tmpans += calcarr2(rv, rvdis); tmpans %= mod; if(tmpans<0) tmpans+=mod; ans += tmpans; ans %= mod; return make_pair(rv, rvdis); } int DistanceSum(int N, int *X, int *Y) { n = N; for(int i=0; i<N; i++) { XX.push_back(X[i]); YY.push_back(Y[i]); } sort(XX.begin(), XX.end()); sort(YY.begin(), YY.end()); for(int i=0; i<N; i++) { X[i] -= XX[0]; Y[i] -= YY[0]; } for(int i=0; i<N; i++) { y[X[i]].push_back(Y[i]); } for(int i=0; i<N; i++) { sort(y[i].begin(), y[i].end()); for(int j:y[i]) { if(y_lst[i].size() > 0 && j == y_lst[i][y_lst[i].size()-1].second + 1) { y_lst[i][y_lst[i].size()-1].second++; } else { y_lst[i].push_back({j, j}); } } } for(int i=0; i<N; i++) { if(y_lst[i].size()) { dfs(i, 0, -1, -1); goto end; } } end:; ans %= mod; if(ans<0) ans+=mod; return ans; }

Compilation message (stderr)

city.cpp: In function 'long long int calcarr(std::vector<long long int>, std::vector<long long int>)':
city.cpp:13:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for(int i=0; i<x.size(); i++) {
      |               ~^~~~~~~~~
city.cpp: In function 'long long int calcarr2(std::vector<long long int>, std::vector<long long int>)':
city.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i=0; i<x.size(); i++) {
      |               ~^~~~~~~~~
city.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > dfs(int, int, int, int)':
city.cpp:39:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  for(int i=0; i<rv.size(); i++) rv[i] = 1;
      |               ~^~~~~~~~~~
city.cpp:40:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |  for(int i=0; i<rv.size(); i++) rvdis[i] = 0;
      |               ~^~~~~~~~~~
city.cpp: In lambda function:
city.cpp:45:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   if(r >= y_lst[nx].size()) r = y_lst[nx].size() - 1;
      |      ~~^~~~~~~~~~~~~~~~~~~
city.cpp:54:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |      for(int j=0; j<tmp.size(); j++) {
      |                   ~^~~~~~~~~~~
city.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |      for(int j=0; j<tmp.size(); j++) {
      |                   ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...