oj.uz

Submission #925379

# Submission time Handle Problem Language Result Execution time Memory
925379 2024-02-11T14:00:53 Z anton Ideal city (IOI12_city) C++17
23 / 100
 26 ms 2904 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 604 KB Output is correct
2 Correct 5 ms 856 KB Output is correct
3 Correct 11 ms 1628 KB Output is correct
4 Correct 11 ms 1628 KB Output is correct
5 Correct 22 ms 2652 KB Output is correct
6 Correct 25 ms 2652 KB Output is correct
7 Correct 22 ms 2900 KB Output is correct
8 Correct 23 ms 2648 KB Output is correct
9 Correct 24 ms 2640 KB Output is correct
10 Correct 26 ms 2904 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 856 KB Output isn't correct
2 Halted 0 ms 0 KB -