oj.uz

Submission #46049

# Submission time Handle Problem Language Result Execution time Memory
46049 2018-04-17T04:15:09 Z mirbek01 Palembang Bridges (APIO15_bridge) C++17
63 / 100
 251 ms 79640 KB 
# include <bits/stdc++.h>
#pragma GCC optimize("Ofast")


# define f first
# define s second

using namespace std;

const int N = 1e5 + 2;

int n, k, cn, sz = 1, root[N];
long long ans = 1e18, p1[N], s1[N], p2[N], s2[N], ss;
int cnt1[2002][2002], cnt2[2002][2002];
long long sum1[2002][2002], sum2[2002][2002];
vector <int> v, v1, v2;
pair < pair <int, int> , pair <char, char> > a[N];
pair <int, pair <int, int> > b[N];

int main(){
      ios_base::sync_with_stdio(0);
      cin.tie(0);

      cin >> k >> n;

      for(int i = 1; i <= n; i ++){
            cin >> a[i].s.f >> a[i].f.f >> a[i].s.s >> a[i].f.s;
            if(a[i].f.f > a[i].f.s) swap(a[i].f.f, a[i].f.s);
            if(a[i].s.f != a[i].s.s) {
                  cn ++;
                  v1.push_back(a[i].f.f), v2.push_back(a[i].f.s);
                  b[cn] = {(a[i].f.f + a[i].f.s + 1), {a[i].f.f, a[i].f.s}};
            } else {
                  ss += abs(a[i].f.s - a[i].f.f);
            }
            v.push_back(a[i].f.f);
            v.push_back(a[i].f.s);
      }

      v1.push_back(-1e9);
      v2.push_back(-1e9);

      sort(b + 1, b + cn + 1);
      sort(v.begin(), v.end());
      v.resize(unique(v.begin(), v.end()) - v.begin());
      sort(v1.begin(), v1.end());
      sort(v2.begin(), v2.end());

      for(int i = 1; i <= cn; i ++){
            p1[i] = p1[i - 1] + v1[i];
            p2[i] = p2[i - 1] + v2[i];
      }
      for(int i = cn; i >= 1; i --){
            s1[i] = s1[i + 1] + v1[i];
            s2[i] = s2[i + 1] + v2[i];
      }

      int pos = 0, ps = 0;

      for(int i = 0; i < v.size(); i ++){
            long long res = 0;
            int x = v[i];
            while(pos + 1 <= cn && v1[pos + 1] <= x) pos ++;
            while(ps + 1 <= cn && v2[ps + 1] <= x) ps ++;
            res += x * 1ll * pos - p1[pos];
            res += x * 1ll * ps - p2[ps];
            res += s1[pos + 1] - x * 1ll * (cn - pos);
            res += s2[ps + 1] - x * 1ll * (cn - ps);
            ans = min(ans, res + cn + ss);
      }

      if(k == 2){
            long long mn = 1e18;

            for(int i = 0; i < v.size(); i ++){
                  for(int j = 1; j <= cn; j ++){
                        if(b[j].s.f <= v[i])
                              sum1[i][j] += b[j].s.f, cnt1[i][j] ++;
                        else
                              sum2[i][j] += b[j].s.f, cnt2[i][j] ++;
                        if(b[j].s.s <= v[i])
                              sum1[i][j] += b[j].s.s, cnt1[i][j] ++;
                        else
                              sum2[i][j] += b[j].s.s, cnt2[i][j] ++;
                        sum1[i][j] += sum1[i][j - 1];
                        cnt1[i][j] += cnt1[i][j - 1];
                        sum2[i][j] += sum2[i][j - 1];
                        cnt2[i][j] += cnt2[i][j - 1];
                  }
            }

            for(int i = 0; i < v.size(); i ++){
                  ps = 0;
                  for(int j = i + 1; j < v.size(); j ++){
                        long long res = 0;
                        int x = (v[i] + v[j] + 1);
                        while(b[ps + 1].f <= x && ps + 1 <= cn) {
                              ps ++;
                        }
                        res += v[i] * 1ll * cnt1[i][ps] - sum1[i][ps];
                        res += sum2[i][ps] - v[i] * 1ll * cnt2[i][ps];
                        res += v[j] * 1ll * (cnt1[j][cn] - cnt1[j][ps]) - (sum1[j][cn] - sum1[j][ps]);
                        res += (sum2[j][cn] - sum2[j][ps]) - v[j] * 1ll *(cnt2[j][cn] - cnt2[j][ps]) ;
                        if(mn > res) mn = res;
                  }
            }
            ans = min(ans, mn + cn + ss);
      }

      cout << ans;
//      cin.get(); cin.get();
}
/***
2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7
***/

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:60:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i = 0; i < v.size(); i ++){
                      ~~^~~~~~~~~~
bridge.cpp:75:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i ++){
                            ~~^~~~~~~~~~
bridge.cpp:92:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < v.size(); i ++){
                            ~~^~~~~~~~~~
bridge.cpp:94:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                   for(int j = i + 1; j < v.size(); j ++){
                                      ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 536 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 2 ms 776 KB Output is correct
7 Correct 3 ms 776 KB Output is correct
8 Correct 2 ms 776 KB Output is correct
9 Correct 3 ms 776 KB Output is correct
10 Correct 3 ms 776 KB Output is correct
11 Correct 2 ms 776 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 776 KB Output is correct
2 Correct 3 ms 776 KB Output is correct
3 Correct 2 ms 776 KB Output is correct
4 Correct 2 ms 776 KB Output is correct
5 Correct 2 ms 776 KB Output is correct
6 Correct 3 ms 776 KB Output is correct
7 Correct 2 ms 836 KB Output is correct
8 Correct 3 ms 836 KB Output is correct
9 Correct 3 ms 836 KB Output is correct
10 Correct 3 ms 836 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 38 ms 8256 KB Output is correct
13 Correct 81 ms 8256 KB Output is correct
14 Correct 69 ms 8256 KB Output is correct
15 Correct 55 ms 8256 KB Output is correct
16 Correct 50 ms 8256 KB Output is correct
17 Correct 62 ms 8256 KB Output is correct
18 Correct 59 ms 8256 KB Output is correct
19 Correct 82 ms 8256 KB Output is correct
20 Correct 49 ms 8256 KB Output is correct
21 Correct 75 ms 8256 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8256 KB Output is correct
2 Correct 2 ms 8256 KB Output is correct
3 Correct 2 ms 8256 KB Output is correct
4 Correct 7 ms 8256 KB Output is correct
5 Correct 4 ms 8256 KB Output is correct
6 Correct 3 ms 8256 KB Output is correct
7 Correct 2 ms 8256 KB Output is correct
8 Correct 6 ms 8256 KB Output is correct
9 Correct 7 ms 8256 KB Output is correct
10 Correct 6 ms 8256 KB Output is correct
11 Correct 2 ms 8256 KB Output is correct
12 Correct 6 ms 8256 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8256 KB Output is correct
2 Correct 2 ms 8256 KB Output is correct
3 Correct 2 ms 8256 KB Output is correct
4 Correct 6 ms 8256 KB Output is correct
5 Correct 4 ms 8256 KB Output is correct
6 Correct 3 ms 8256 KB Output is correct
7 Correct 2 ms 8256 KB Output is correct
8 Correct 6 ms 8256 KB Output is correct
9 Correct 6 ms 8256 KB Output is correct
10 Correct 6 ms 8256 KB Output is correct
11 Correct 2 ms 8256 KB Output is correct
12 Correct 6 ms 8256 KB Output is correct
13 Correct 2 ms 8256 KB Output is correct
14 Correct 9 ms 8256 KB Output is correct
15 Correct 243 ms 78460 KB Output is correct
16 Correct 2 ms 78460 KB Output is correct
17 Correct 5 ms 78460 KB Output is correct
18 Correct 37 ms 78460 KB Output is correct
19 Correct 3 ms 78460 KB Output is correct
20 Correct 249 ms 79496 KB Output is correct
21 Correct 230 ms 79612 KB Output is correct
22 Correct 235 ms 79612 KB Output is correct
23 Correct 3 ms 79612 KB Output is correct
24 Correct 248 ms 79636 KB Output is correct

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 79636 KB Output is correct
2 Correct 2 ms 79636 KB Output is correct
3 Correct 2 ms 79636 KB Output is correct
4 Correct 6 ms 79636 KB Output is correct
5 Correct 4 ms 79636 KB Output is correct
6 Correct 3 ms 79636 KB Output is correct
7 Correct 2 ms 79636 KB Output is correct
8 Correct 6 ms 79636 KB Output is correct
9 Correct 6 ms 79636 KB Output is correct
10 Correct 6 ms 79636 KB Output is correct
11 Correct 2 ms 79636 KB Output is correct
12 Correct 7 ms 79636 KB Output is correct
13 Correct 2 ms 79636 KB Output is correct
14 Correct 8 ms 79636 KB Output is correct
15 Correct 249 ms 79636 KB Output is correct
16 Correct 2 ms 79636 KB Output is correct
17 Correct 6 ms 79636 KB Output is correct
18 Correct 37 ms 79636 KB Output is correct
19 Correct 2 ms 79636 KB Output is correct
20 Correct 251 ms 79640 KB Output is correct
21 Correct 229 ms 79640 KB Output is correct
22 Correct 236 ms 79640 KB Output is correct
23 Correct 2 ms 79640 KB Output is correct
24 Correct 244 ms 79640 KB Output is correct
25 Incorrect 45 ms 79640 KB Output isn't correct
26 Halted 0 ms 0 KB -