Submission #925379

#	Time	Username	Problem	Language	Result	Execution time	Memory
925379		anton	Ideal city (IOI12_city)	C++17	23 / 100	26 ms	2904 KiB

city

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>

vector<pii> layers;
const long long mod = 1000000000;

const ll INF = (1LL<<31LL)-1LL;

int x_range= INF, y_range=  INF;

int DistanceSum(int N, int *X, int *Y) {
    for(int i = 0; i<N; i++){
        x_range = min(X[i], x_range);
        y_range = min(Y[i], y_range);
    }
    for(int i = 0; i<N; i++){
        X[i] -= x_range;
        Y[i] -= y_range;
    }

    layers.resize(N, {INF, -INF});

  for(int i = 0; i<N; i++){
    layers[X[i]].first = min(layers[X[i]].first, Y[i]);
    layers[X[i]].second = max(layers[X[i]].second, Y[i]);
  }

  unordered_map<int, pll> vals;

    long long res = 0;
    for(int i = 0; i<N; i++){
        if(layers[i].second>= -INF){
            unordered_map<int, pll> cur_vals;
            if(i>0){
                pii prev_layer = layers[i-1];
                for(int y = layers[i].first; y<=layers[i].second; y++){
                    int correspondant=  min(prev_layer.second,max(y, prev_layer.first));
                    cur_vals[y].first = vals[correspondant].first;
                    cur_vals[y].second = vals[correspondant].second + vals[correspondant].first*(abs(y-correspondant)+1);
                    
                    res+=cur_vals[y].second;
                }
            }
            ll d= 0;
            for(int y = layers[i].first; y<=layers[i].second; y++){
                d+= y-layers[i].first;
            }
            ll left= 0;
            ll right = layers[i].second-layers[i].first+1;
            ll sum_left= 0;
            for(int y = layers[i].first; y<=layers[i].second; y++){
                cur_vals[y].first+=left+right;
                cur_vals[y].second+=d;
                
                res+=sum_left;
                right--;
                left++;
                sum_left+=left;
                d+= left-right;
                //cout<<sum_left-left<<" "<<cur_vals[y].first<<" "<<cur_vals[y].second<<" | ";
            }
            //cout<<endl;
            swap(vals, cur_vals);
        }
    }

  return res%mod;

}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 21
• Subtask 3: 23 / 23
• Subtask 4: 0 / 45